N - Increasing Gradually

ストーリー

Imosちゃん「私にも問題作らせて～！」

問題文

広義単調増加する長さ $N$ の数列 $A=(A_1, A_2, ..., A_N)$ が与えられます．
$Q$ 行にわたってクエリが与えられるので，順に処理してください．各クエリは以下のいずれかの形式で与えられます．

• 1 x : 数列 $A$ に存在する数のうち，$x$ 以上の最小の数を求めてください．
• 2 x y : $N-x+1$ 個の要素 $A_x, A_{x+1}, ..., A_N$ 全てに $y$ を加算してください．

制約

• 入力はすべて整数
• $1 \leq N, Q \leq 2 \cdot 10^5$
• $1 \leq A_1 \leq A_2 \leq ... \leq A_N \leq 10^9$
• クエリが 1 x の形式で与えられたとき，
  • $1 \leq x \leq 2 \cdot 10^9$
• クエリが 2 x y の形式で与えられたとき，
  • $1 \leq x \leq N$
  • $1 \leq y \leq 1000$

入力

入力は以下の形式で標準入力から与えられる．

$N~Q$

$A_1~A_2~...~A_N$

$Query_1$

$Query_2$

$...$

$Query_Q$

ここで $Query_i$ は $i$ 番目のクエリを表し，以下のいずれかの形式で与えられる．

$1~x$

$2~x~y$

出力

1 x の形式で与えられるクエリの個数が $X$ 個であるとして，$X$ 行出力してください．
$i$ 行目には 1 x の形式で与えられたクエリのうち $i$ 番目の答えを出力してください．ただし，答えが存在しない場合もあるので，その時は -1 を出力してください．

入力例1

5 6
2 3 5 7 11
1 6
2 3 2
2 5 12
1 22
2 2 10
1 15
Copy

出力例1

7
25
17
Copy

• $1$ 番目のクエリ : 数列 $A=(2, 3, 5, 7, 11)$ より，$6$ 以上の最小の数は $7$ なので，出力すべきは 7 です．
• $2$ 番目のクエリ : 数列 $A=(2, 3, 7, 9, 13)$ となります．
• $3$ 番目のクエリ : 数列 $A=(2, 3, 7, 9, 25)$ となります．
• $4$ 番目のクエリ : $22$ 以上の最小の数は $25$ なので，出力すべきは 25 です．
• $5$ 番目のクエリ : 数列 $A=(2, 13, 17, 19, 35)$ となります．
• $6$ 番目のクエリ : $15$ 以上の最小の数は $17$ なので，出力すべきは 17 です．

アフターストーリー

Imosちゃん「みんなも気が向いたらWriter,Testerになってみて！　またどこかで会おうね！」