AT_arc231_c [ARC231C] One Sky, Many Stars

For length- $ N $ sequences of non-negative integers $ x = (x_1, x_2, \cdots, x_N), d = (d_1, d_2, \cdots, d_N) $ , consider the following problem **Stargazing**. Here, $ x_1 < x_2 < \cdots < x_N $ . > **Stargazing** > There are $ N $ people numbered from $ 1 $ to $ N $ on a number line. Person $ i $ ( $ 1 \leq i \leq N $ ) is at coordinate $ x_i $ . Also, there are one or more stars on the number line, which can be regarded as points. > Regarding the arrangement of the stars, person $ i $ testifies that "the distance to the star nearest to me is $ d_i $ ." There may be multiple stars at the minimum distance from the person. > Determine whether there exists an arrangement of the stars that does not contradict the testimonies of the $ N $ people, and output `Yes` if it exists and `No` otherwise. You are given length- $ N $ sequences of non-negative integers $ A = (A_1, A_2, \cdots, A_N), B = (B_1, B_2, \cdots, B_N) $ . Here, $ A_1 < A_2 < \cdots < A_N $ holds. Process $ Q $ queries. The $ j $ -th query ( $ 1 \leq j \leq Q $ ) is represented as follows. - You are given an integer $ P_j $ between $ 1 $ and $ N $ , inclusive, and a non-negative integer $ S_j $ . Change $ B_{P_j} $ to $ S_j $ . Then, solve **Stargazing** with $ x, d $ being $ A, B $ , respectively. The change of $ B_{P_j} $ carries over to subsequent queries. Solve $ T $ test cases per input file.

The input is given from Standard Input in the following format. Here, $ \mathrm{case}_i $ ( $ 1 \leq i \leq T $ ) denotes the $ i $ -th test case. > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ Each test case is given in the following format: > $ 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 the answers in the order $ \mathrm{case}_1, \mathrm{case}_2, \cdots, \mathrm{case}_T $ . For each test case, output the answers to **Stargazing** for the $ 1, 2, \cdots, Q $ -th queries, separated by newlines.

### Sample Explanation 1 For the first test case, each query goes as follows. - After the change in the first query, $ A = (2, 4, 8), B = (3, 3, 0) $ . The answer to **Stargazing** with $ x, d $ being $ A, B $ , respectively, is `Yes`. For example, if stars are at coordinates $ -1, 7, 8 $ as in the figure below, the conditions are satisfied. - After the change in the second query, $ A = (2, 4, 8), B = (7, 3, 0) $ . The answer to **Stargazing** with $ x, d $ being $ A, B $ , respectively, is `No`. This is because it can be shown that there exists no arrangement of the stars satisfying the conditions.  ### 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 $ ) - The sum of $ N $ over the $ T $ test cases is at most $ 200\,000 $ . - The sum of $ Q $ over the $ T $ test cases is at most $ 200\,000 $ . - All input values are integers.