2306. K大数查询

有 $N$ 个位置,$M$ 个操作。每个位置可以同时存储多个数。

操作有两种,每次操作:

  • 如果是 1 a b c 的形式,表示在第 $a$ 个位置到第 $b$ 个位置,每个位置加入一个数 $c$。
  • 如果是 2 a b c 的形式,表示询问从第 $a$ 个位置到第 $b$ 个位置,第 $c$ 大的数是多少。

输入格式

第一行包含两个整数 $N,M$。

接下来 $M$ 行,每行包含一条指令,形如 1 a b c2 a b c

输出格式

输出每个询问的结果,每个结果占一行。

数据范围

$1 \le N,M \le 50000$,
$1 \le a \le b \le N$,
$1$ 操作中的 $c$ 的绝对值不超过 $N$,
$2$ 操作中 $c$ 满足 $1 \le c \le 2^{31}-1$。

所有操作保证合法。

输入样例:

2 5
1 1 2 1
1 1 2 2
2 1 1 2
2 1 1 1
2 1 2 3

输出样例:

1
2
1

样例解释

第一个操作后位于位置 $1$ 的数只有 $1$,位于位置 $2$ 的数也只有 $1$。

第二个操作后位于位置 $1$ 的数有 $1、2$,位于位置 $2$ 的数也有 $1、2$。

第三次询问位置 $1$ 到位置 $1$ (也就是位置 $1$)中第 $2$ 大的数,答案是 $1$。

第四次询问位置 $1$ 到位置 $1$ (也就是位置 $1$)中第 $1$ 大的数,答案是 $2$。

第五次询问位置 $1$ 到位置 $2$ 中第 $3$ 大的数,答案是 $1$。