AT_pakencamp_2022_day2_h Habatu

パ研部員が一列に $ 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 $ が派閥争いを始めたとき最後に残る派閥を求めます。 各思考実験の結果を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ B_1 $ $ B_2 $ $ \ldots $ $ B_{N - 1} $ $ Q $ $ T_1 $ $ P_1 $ $ V_1 $ $ L_1 $ $ R_1 $ $ T_2 $ $ P_2 $ $ V_2 $ $ L_2 $ $ R_2 $ $ \vdots $ $ T_Q $ $ P_Q $ $ V_Q $ $ L_Q $ $ R_Q $

$ Q $ 行出力せよ。 $ j \ (1 \leq j \leq Q) $ 行目には、 $ j $ 日目における派閥太郎君の思考実験において最後に残るのを派閥 $ a $ としたとき $ a $ を出力せよ。

### 小課題 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 $ 点) 追加の制約はない ### Sample Explanation 1 例として $ 1 $ 日目の思考実験について考えます。 $ 1 $ 日目の終わりにおける部員 $ 4, 5 $ のパソコン力はそれぞれ $ 7, 9 $ です。よって、 $ 1 $ 日目の思考実験において最後に残るのは派閥 $ 5 $ となります。 この入出力例は小課題 5 の制約を満たします。 ### Sample Explanation 2 この入出力例は小課題 2, 5 の制約を満たします。 ### Sample Explanation 3 この入出力例は小課題 3, 5 の制約を満たします。 ### Sample Explanation 4 この入出力例は小課題 4, 5 の制約を満たします。 ### Sample Explanation 5 この入出力例は小課題 5 の制約を満たします。 ### Constraints - 入力は全て整数 - いずれの時点においても、仲良し度は相異なる - $ 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) $