問題文

パ研部員が一列に N 人並んでいます。左から i \ (1 \leq i \leq N) 番目の部員を部員 i と呼ぶことにします。現在の部員 i のパソコン力は A_i です。隣り合う部員同士には仲良し度という指標が存在し、 1 \leq i \leq N - 1 について現在の部員 i と部員 i + 1 の仲良し度は B_i です。ここで B_i は相異なります。

パ研部員は派閥争いが大好きです。普段は派閥争いが禁止されていますが、万が一派閥争いが起こってしまったときのことを考えてみましょう。

人 l, l + 1, \cdots , r \ (1 \leq l \leq r \leq N) が派閥争いを始めると、以下の事柄が起こります。

• はじめ、派閥 l, l + 1, \cdots ,r が存在し、部員 i \ (l \leq i \leq r) は派閥 i に属する。それ以外の部員は派閥に属さない。
• 派閥 a, b \ (l \leq a < b \leq r) の仲良し度は、以下のように定義される。

  どの時点においても、派閥 a に人 i が所属し、派閥 b に人 i+1 が所属しているような i は高々 1 つ存在することが証明できる。仲良し度は、このような i が存在しない場合 -10^{100} であり、存在する場合 B_i である。

• 派閥が 1 つになるまで、以下のイベントが繰り返される。

  仲良し度が最大である 2 派閥 a, b \ (a < b) を考える。各派閥に所属する人のパソコン力の総和を s, t とする。このとき s \geq t なら派閥 b に所属する人が全員派閥 a に所属を変え、 s < t なら派閥 a に所属する人が全員派閥 b に所属を変える。また、所属する人がいなくなった派閥は消滅する。

パ研の活動は明日からの Q 日の間活発なので、部員のパソコン力や仲良し度は頻繁に変わります。具体的には、 j \ (1 \leq j \leq Q) 日目には以下の変化が起こります。

• T_j = 1 の場合、部員 P_j のパソコン力が V_j になる。
• T_j = 2 の場合、部員 P_j と部員 P_j + 1 の間の仲良し度が V_j になる。

ただし、いずれの時点においても部員同士の仲良し度は相異なることが保証されます。

派閥争いを想像するのが大好きな派閥太郎君は、毎日派閥争いの思考実験を行います。具体的には、 j \ (1 \leq j \leq Q) 日目の終わりには、部員 L_j, L_j + 1, \cdots ,R_j が派閥争いを始めたとき最後に残る派閥を求めます。

各思考実験の結果を求めてください。

制約

• 入力は全て整数
• いずれの時点においても、仲良し度は相異なる
• 2 \leq N \leq 10^5
• 1 \leq Q \leq 10^5
• 1 \leq A_i \leq 10^9 \ (1 \leq i \leq N)
• 1 \leq B_i \leq 10^9 \ (1 \leq i \leq N - 1)
• T_j \in \{1, 2\} \ (1 \leq j \leq Q)
• T_j = 1 のとき 1 \leq P_j \leq N \ (1 \leq j \leq Q)
• T_j = 2 のとき 1 \leq P_j \leq N - 1 \ (1 \leq j \leq Q)
• 1 \leq V_j \leq 10^9 \ (1 \leq j \leq Q)
• 1 \leq L_j \leq R_j \leq N \ (1 \leq j \leq Q)

小課題

1. (100 点) Q = 1
2. (150 点) T_j = 1, L_j = 1, R_j = N \ (1 \leq j \leq Q)
3. (350 点) T_j = 2, L_j = 1, R_j = N \ (1 \leq j \leq Q)
4. (200 点) T_j = 1, V_j = A_{P_j} \ (1 \leq j \leq Q)
5. (100 点) 追加の制約はない

入力例 1

5
5 9 9 7 9
6 7 3 4
3
1 4 7 4 5
2 4 10 1 3
1 1 6 1 3

出力例 1

5
2
2

例として 1 日目の思考実験について考えます。1 日目の終わりにおける部員 4, 5 のパソコン力はそれぞれ 7, 9 です。よって、 1 日目の思考実験において最後に残るのは派閥 5 となります。

この入出力例は小課題 5 の制約を満たします。

入力例 2

8
14 10 12 20 18 1 6 13
2 16 1 3 4 12 11
5
1 2 3 1 8
1 3 8 1 8
1 1 4 1 8
1 7 15 1 8
1 4 19 1 8

出力例 2

8
8
8
7
7

この入出力例は小課題 2, 5 の制約を満たします。

入力例 3

8
10 17 13 17 16 1 19 8
11 1 9 4 2 12 10
5
2 2 7 1 8
2 4 15 1 8
2 3 5 1 8
2 2 13 1 8
2 6 14 1 8

出力例 3

4
4
2
2
2

この入出力例は小課題 3, 5 の制約を満たします。

入力例 4

8
11 11 2 2 10 5 2 15
9 1 10 19 7 14 20
3
1 1 11 8 8
1 1 11 4 6
1 1 11 2 6

出力例 4

8
5
5

この入出力例は小課題 4, 5 の制約を満たします。

入力例 5

20
30 95 72 93 69 100 45 51 7 19 40 61 73 51 98 71 25 51 15 91
20 69 94 58 63 70 80 17 66 10 83 48 40 86 23 67 60 44 96
6
2 9 71 6 15
1 2 46 11 15
1 6 15 6 19
2 8 8 1 13
2 8 26 6 18
1 9 31 5 14

出力例 5

12
12
12
4
12
8

この入出力例は小課題 5 の制約を満たします。