Range k-th Largest Query

問題

要素数が $N$ の配列 $A$ がある。この配列に対して $Q$ 個のクエリが与えられるので順に処理せよ。
クエリは以下の通りである。

• 1 x : $A$ の全ての要素に対して $x$ だけ加算する。
• 2 l r k: 閉区間 $[l,r]$ での $A$ の $k$ 番目に大きい値を出力する。

制約

• $1 \le N,\ Q \le 10^5$
• $-10^9 \le A_i(1 \le i \le N),\ x \le 10^9$
• $1 \le l,\ r \le N$
• $1 \le k \le r - l + 1$
• $N,\ Q,\ A_i,\ x,\ l,\ r,\ k \in \Z$

入力

ただし、$Query_q$ は以下のいずれかの形式で与えられる。

出力

2番目の形式のクエリに対し、答えを出力せよ。また、クエリごとに改行せよ。

入力例 1

5 4
2 7 1 8 2
1 4
2 1 3 2
1 -7
2 3 5 1

出力例 1

6
5

$Query_1$: $A$ の要素全てに4を加える。$A = [6, 11, 5, 12, 6]$
$Query_2$: $A$ の部分配列 $A[1..3] = [6, 11, 5]$, ここで2番目に大きいのは6
$Query_3$: $A$ の要素全てに7を引く。$A = [-1, 4, -2, 5, -1]$
$Query_4$: $A$ の部分配列 $A[3..5] = [-2, 5, -1]$, ここで1番目に大きいのは5

入力例 2

6 3
1 2 3 4 5 6
2 1 4 2
1 -7
2 3 5 3

出力例 2

3
-4

入力例 3

3 11
1000000000 1000000000 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
2 1 1 1

出力例 3

11000000000

答えは32-bit整数で収まらないことに注意せよ。