Problem Description

现在有 $ N $ 个城市，每个城市都有一个水池，水池的容量是无限的。初始时，第 $ i $ 个城市的水池有 $ A_i $ 的水量。

共有 $ Q $ 个事件：

第一种事件是：位于$ [L,R] $ 的城市下了一场雨，并用 $ X $ 来表示这场雨的大小，即这些城市的水池里的水会增加 $ X $ 的水量。

第二种事件是：假设 hezlik 初始位于 $ L $，他可以选择一个 $ R(L\leq R) $ 并选择 $ [L,R] $ 这些城市中的恰好 $ K $ 个水池，然后得到这些水池的水。他想收集至少 $P$ 的水量，但是他并不想走太远，请你告诉他最小的 $ R $ 会在哪里。如果不存在的话，请你输出 -1。由于 hezlik 非常善良可爱，在收集完成后会将所有的水放回原来的水池，所以在该事件结束后，并不会对水池的水量造成任何影响。

Input

第一行输入两个整数 $N$ 和 $Q$，表示城市的个数和事件的个数。

第二行输入 $N$ 个整数，表示第 $i$ 个城市的水池初始时的水量 $A_i$。

接下来 $Q$ 行，每行描述一个事件，每行包含四个整数。

如果第一个整数是 $1$，表示这是第一种事件，接下来三个整数表示 $L$，$R$ 和 $X$。

如果第一个整数是 $2$，表示这是第二种事件，接下来三个整数表示 $L$，$K$ 和 $P$。

$1 \leq N, Q \leq 3 \times 10^5$，$1 \leq A_i, X \leq 10^6$，$1 \leq L\leq R\leq N$，$1 \leq K \leq 10$，$1\leq P \leq 10^{18}$。

Output

对于第二种事件，输出最小的 $R$ 即可。

10 5
2 4 2 10 2 5 2 8 5 3
1 4 7 10
2 1 2 35
1 2 4 8
2 3 2 38
2 1 2 44

6
4
-1