Comet OJ

C0835 [ZJOI2013]K大数查询

内存限制：256 MB 时间限制：2000 ms

题目描述

有 $N$ 个位置，$M$ 个操作。操作有两种，每次操作如果是1 a b c的形式表示在第 $a$ 个位置到第 $b$ 个位置，每个位置加入一个数 $c$。如果是2 a b c形式，表示询问从第 $a$ 个位置到第 $b$ 个位置，第 $c$ 大的数是多少。

输入格式

第一行 $N$，$M$。

接下来 $M$ 行，每行形如1 a b c或2 a b c。

输出

输出每个询问的结果。

样例

样例输入 1

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

样例输出 1

1
2
1

提示

【样例说明】

第一个操作后位置 1 的数只有 1， 位置 2 的数也只有 1。 第二个操作后位置 1 的数有 1、2，位置 2 的数也有 1、2 。 第三次询问位置 1 到位置 1 第 2 大的数 是 1。 第四次询问位置 1 到位置 1 第 1 大的数是 2。 第五次询问位置 1 到位置 2 第 3大的数是 1 。‍

【数据规模与约定】

$N,M \le 50000$

$a \le b \le N$

1 操作中 $abs(c) \le N$

2 操作中 $c \le$ max long int