Problem Statement

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.

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.

Input

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

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.