Background

留得残荷听雨声。

Description

某个电阻器内有编号为 1∼n 的 n 个独立水箱，水箱呈圆柱形，底面积为 1 m^2，每个水箱在顶部和底部各有一个阀门，可以让水以 1 m^3/s 的流量通过，每个水箱的上阀门接水龙头，可以无限供应水，下阀门不接东西，可以让水流出。水箱的高度足够高。一开始时第 i 个水箱中有 ai m^3的水。
有两种操作
ti=1、将编号为 y 的水箱的下方阀门与大海通过连通器以一定方式相连，使得这个水箱中恰拥有 x m^3的水，然后关上它的下方阀门，撤去连通器。
ti=2、由于水浸泡过的地方会留下明显的水渍而没有被水浸泡过的地方不会有，Picks 博士可以据此测量出此时第 l 到 r 个水箱的水渍高度，以推断曾经最多有多少水，节约他的建造成本。
现在，他请你来帮他做预实验，你能告诉他每次测量得到的电流大小以及测量得到的最多的水量是多少吗？

Format

Input

第一行两个数：n,m。
接下来一行 n 个数，第 i 个数表示初始时第 i 个水箱内有 ai m^3 的水。
接下来 m 行中，第 i 行第一个数 ti 表示操作类型：
若 ti=1，则接下来两个整数 yi，xi，表示将编号为 yi 的水箱与大海连接，使这个水箱中恰有 xi m^3 的水。
若 ti=2，则接下来两个整数 li ri，表示测量此时在第 li 到 ri 个水箱中的水渍高度的最大值。

Output

对于每个 ti=2，输出一个整数表示在第 li 到 ri 个水箱中的水渍高度的最大值。(单位为 m)。
对于 30% n<=3000,m<=3000;
对于 100%,n<=100000,m<=100000

Sample

Input

5 2 
1 2 3 4 5 
1 3 6 
2 1 5 

Output

6

Limitation

1s, 256000KiB for each test case.

Hint

Source

CDQZ TEST