AT_arc231_c [ARC231C] One Sky, Many Stars
Description
長さが $ N $ の非負整数列 $ x = (x_1, x_2, \cdots, x_N), d = (d_1, d_2, \cdots, d_N) $ に対して，以下の問題 **Stargazing** を考えます．ここで， $ x_1 < x_2 < \cdots < x_N $ とします．
> **Stargazing**
> $ 1 $ から $ N $ までの番号が付けられた $ N $ 人の人が数直線上にいます．人 $ i $ ( $ 1 \leq i \leq N $ ) は座標 $ x_i $ にいます．また，数直線上には点とみなすことができる星が $ 1 $ つ以上存在します．
> 星の配置について，人 $ i $ は「自分に一番近い星までの距離は $ d_i $ である」と証言しています．なお，自分との距離が最短となる星が複数存在しても構いません．
> $ N $ 人の証言に矛盾しないような星の配置が存在するか判定し，存在する場合は `Yes` を，そうでない場合は `No` を出力してください．
長さが $ N $ の非負整数列 $ A = (A_1, A_2, \cdots, A_N), B = (B_1, B_2, \cdots, B_N) $ が与えられます．ここで， $ A_1 < A_2 < \cdots < A_N $ が成立します． $ Q $ 個のクエリを処理してください． $ j $ 番目 ( $ 1 \leq j \leq Q $ ) のクエリは以下のように表されます．
- $ 1 $ 以上 $ N $ 以下の整数 $ P_j $ と非負整数 $ S_j $ が与えられます． $ B_{P_j} $ を $ S_j $ に変更してください．その後， $ x, d $ をそれぞれ $ A, B $ とした場合の **Stargazing** を解いてください．なお， $ B_{P_j} $ の変更は以降のクエリにも引き継がれます．
$ 1 $ つの入力ファイルにつき， $ T $ 個のテストケースを解いてください．
Input Format
入力は以下の形式で標準入力から与えられる．ここで， $ \mathrm{case}_i $ ( $ 1 \leq i \leq T $ ) は $ i $ 番目のテストケースを意味する．
> $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $
各テストケースは以下の形式で与えられる．
> $ N $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $ $ B_1 $ $ B_2 $ $ \cdots $ $ B_N $ $ Q $ $ P_1 $ $ S_1 $ $ P_2 $ $ S_2 $ $ \vdots $ $ P_Q $ $ S_Q $
Output Format
$ \mathrm{case}_1, \mathrm{case}_2, \cdots, \mathrm{case}_T $ の順に答えを出力せよ．それぞれのテストケースにおいては， $ 1, 2, \cdots, Q $ 番目のクエリにおける **Stargazing** の答えを改行区切りで出力せよ．
Explanation/Hint
### Sample Explanation 1
$ 1 $ 番目のテストケースについて，それぞれのクエリでは以下のようになります．
- $ 1 $ 番目のクエリで変更した後， $ A = (2, 4, 8), B = (3, 3, 0) $ です． $ x, d $ をそれぞれ $ A, B $ とした場合の **Stargazing** の答えは `Yes` です．例えば，以下の図のように星が座標 $ -1, 7, 8 $ にあるならば条件を満たします．
- $ 2 $ 番目のクエリで変更した後， $ A = (2, 4, 8), B = (7, 3, 0) $ です． $ x, d $ をそれぞれ $ A, B $ とした場合の **Stargazing** の答えは `No` です．条件を満たす星の配置が存在しないことが示せるためです．
### Constraints
- $ 1 \leq T \leq 10 $
- $ 1 \leq N \leq 150\,000 $
- $ 0 \leq A_1 < A_2 < \cdots < A_N \leq 10^9 $
- $ 0 \leq B_i \leq 10^9 $ ( $ 1 \leq i \leq N $ )
- $ 1 \leq Q \leq 150\,000 $
- $ 1 \leq P_j \leq N $ ( $ 1 \leq j \leq Q $ )
- $ 0 \leq S_j \leq 10^9 $ ( $ 1 \leq j \leq Q $ )
- $ T $ 個のテストケースにおける $ N $ の総和は $ 200\,000 $ 以下
- $ T $ 個のテストケースにおける $ Q $ の総和は $ 200\,000 $ 以下
- 入力される値はすべて整数である