题目描述

Petya 非常喜欢果冻糖。有 $n$ 家商店出售果冻糖，第 $i$ 家商店出售的果冻糖美味度为 $a_i$，且每家商店都有无限多个这种果冻糖。Petya 只吃果冻糖，因此他的朋友 Sasha 正认真监督他的饮食。

每天会发生两种事件之一：

1. 对编号从 $l$ 到 $r$ 的商店，其果冻糖美味度增加 $x$：

   $$a_i := a_i+x \quad \text{for all } i \in [l,r].$$

2. 购买果冻糖。Petya 会按顺序查看编号从 $l$ 到 $r$ 的商店。在每家商店，他可以选择恰好买一个果冻糖，也可以跳过不买。

   假设 Petya 从商店 $l \le i_1 < i_2 < \cdots < i_m \le r$ 中购买了果冻糖。我们按购买顺序记这些果冻糖的美味度为 $b_j := a_{i_j}$。

   在所有可能的购买方案中，Petya 会选择使序列 $b$ 字典序最大的方案。

   购买之后，Sasha 想知道 $b_k$ 的值，也就是 Petya 会购买的第 $k$ 个果冻糖的美味度；或者判断所选序列长度是否小于 $k$。

请帮助 Sasha 弄清 Petya 的饮食！

回忆：若存在某个位置 $i$，使得 $b_i>c_i$ 且对所有 $j<i$ 均有 $b_j=c_j$，则序列 $(b_1,b_2,\ldots,b_m)$ 的字典序大于 $(c_1,c_2,\ldots,c_k)$；此外，如果 $(b_1,\ldots,b_k)$ 是 $(c_1,\ldots,c_k)$ 的前缀且 $m>k$，也认为前者字典序更大。

输入格式

第一行包含两个整数 $n,q$（$1 \le n,q \le 500000$），表示商店数量和天数。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1 \le a_i \le 10^9$），表示初始美味度。

接下来 $q$ 行描述询问。每行首先给出整数 $t_i$（$1 \le t_i \le 2$），表示第 $i$ 个询问的类型。

若 $t=1$，随后给出三个整数 $l_i,r_i,x_i$（$1 \le l_i \le r_i \le n$，$1 \le x_i \le 10^9$），表示编号 $l_i,l_i+1,\ldots,r_i$ 的商店中果冻糖美味度都增加 $x_i$。

若 $t=2$，随后给出三个整数 $l_i,r_i,k_i$（$1 \le l_i \le r_i \le n$，$1 \le k_i \le n$），表示 Petya 查看编号 $l_i,l_i+1,\ldots,r_i$ 的商店，Sasha 想知道 Petya 会购买的第 $k_i$ 个果冻糖的美味度。

输出格式

对于每个第二类询问，如果 Petya 买到的果冻糖数量少于 $k$，输出 -1；否则输出 Petya 买到的第 $k$ 个果冻糖的美味度。

样例

样例输入 1

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

样例输出 1

2
3
3
-1

样例输入 2

5 6
5 2 5 5 2
1 3 5 10
2 2 2 1
2 3 5 1
1 2 3 11
2 3 4 1
2 2 4 1

样例输出 2

2
15
26
26

样例解释

考虑第一个样例。

初始美味度为 $[1,3,2,3,2]$。

第一次询问中，Petya 从整个数组中购买果冻糖。他能得到的字典序最大序列为 $[3,3,2]$。询问第三个元素，因此答案为 $2$。

第二次询问中，Petya 从区间 $[3,5]$ 购买果冻糖。他能得到的字典序最大序列为 $[3,2]$。询问第一个元素，因此答案为 $3$。

随后第三家商店的美味度增加 $2$，美味度变为 $[1,3,4,3,2]$。

接下来，Petya 从区间 $[2,5]$ 购买果冻糖。他能得到的字典序最大序列为 $[4,3,2]$。询问第二个元素，因此答案为 $3$。

最后一次询问中，Petya 从整个数组中购买果冻糖。他能得到的字典序最大序列为 $[4,3,2]$。询问第四个元素，因为不存在，所以输出 $-1$。

计分方式

测试数据包含七个测试组。只有当某组所有测试点以及该组要求的若干前置组均通过时，才能获得该组分数。注意，某些测试组不要求通过样例测试。离线测试表示该组测试结果会在比赛结束后才可见。

令 $m$ 表示当前询问中 Petya 会购买的果冻糖数量。