Migrated from Lutece 3137 Way to home

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Tag：树套树模板题/整体二分

这里就介绍下黄油土豆的简单做法

起火

跳舞

加热石头

为每个土豆起名字

怀着断肠的哀思，把铝箔包住的土豆投入石头里（增加风味）

等待

泪目

等待

擦眼泪

等待

跨过悲痛后人会变得成熟（土豆也熟）

等待

等够了，要收拾肚子里的虫子了

黑须太一正在庭院中制作黄油土豆（流程如上），他一共点燃了 $n$ 个火堆用来加热土豆，火堆从左到右编号为 $1\sim n$ 。

他一共会进行 $m$ 次操作，每次操作形如：

• 1 l r c，在编号为 $[l,r]$ 的火堆中各加入一个美味度为 $c$ 的土豆。
• 2 l r k，查询当前在编号为 $[l,r]$ 的火堆中的所有土豆中，美味度第 $k$ 大的值是多少。

如果你能正确回答他的问题，他兴许会给你几个土豆来收拾你肚子里的虫子的说。

Input

输入的第一行包括两个正整数 $n,m$ ，分别表示火堆的个数以及操作的个数。

接下来的 $m$ 行，每行四个整数表示一次操作，格式和意义如题面所述。

Output

对于每个第二种类型的操作，输出一行一个整数表示答案。

Samples

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

Constraints

$1\le n,m\le 5\times 10^4,1\le l\le r\le n,|c|\le n,1\le k<2^{63}$

数据保证对于所有第二种类型的操作， $k$ 均不会超过当前编号为 $[l,r]$ 的火堆中的土豆的总个数。

Resources

2024 UESTC ICPC Training for Data Structures