AT_arc231_c.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.

对于长度为 $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$ 处。此外，数轴上还存在一个或多个“星星”，可视为点。
关于星星的排布，第 $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$）的形式如下：

• 给定一个整数 $P_j$（$1 \leq P_j \leq N$）和一个非负整数 $S_j$，将 $B_{P_j}$ 修改为 $S_j$；然后以 $x = A$、$d = B$ 作为输入求解 观星（Stargazing） 问题。对 $B_{P_j}$ 的修改将持续影响后续所有查询。

每组输入文件需处理 $T$ 个测试用例。

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$

输入从标准输入给出，格式如下。其中，$\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 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.

按 $\mathrm{case}_1, \mathrm{case}_2, \cdots, \mathrm{case}_T$ 的顺序输出答案。对于每个测试用例，依次输出 Stargazing 问题中第 $1, 2, \cdots, Q$ 个查询的答案，各答案之间用换行符分隔。

Sample 1 Explanation:
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.

样例 1 解释：
对于第一个测试用例，每次查询的过程如下：

• 第一次查询执行修改后，$A = (2, 4, 8),\ B = (3, 3, 0)$。此时以 $x = A$、$d = B$ 作为输入调用 Stargazing 问题，答案为 Yes。例如，若恒星位于坐标 $-1,\ 7,\ 8$（如下图所示），则所有条件均被满足。
• 第二次查询执行修改后，$A = (2, 4, 8),\ B = (7, 3, 0)$。此时以 $x = A$、$d = B$ 作为输入调用 Stargazing 问题，答案为 No。这是因为可以证明：不存在任何恒星排布方式满足全部条件。

约束条件

• $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$。
• 所有输入值均为整数。