Extended Sequences Comparison

Consider two sequences $X = \{x_1,x_2,\cdots,x_n\}$ and $Y = \{y_1,y_2,\cdots,y_m\}$. A sequence $B$ is said to be an extension of $A$ if there exists a sequence of positive integers $L = \{l_1,l_2,\cdots,l_{|A|}\}$ such that replacing each element $a_i$ of $A$ by $l_i$ copies of $a_i$ (and concatenating them in order) produces $B$.

For example,

• $\{1,3,3,3,2,2,2\}$ is an extension of $\{1,3,3,2\}$ (one may take $L = \{1,1,2,3\}$ or $\{1,2,1,3\}$).
• $\{1,3,3,2\}$ is not an extension of $\{1,3,3,3,2\}$, and $\{1,2,3\}$ is not an extension of $\{1,3,2\}$.

Now, you are given two sequences $X$ and $Y$. You need to decide whether there exist two extensions $F$ of $X$ and $G$ of $Y$, both of length $l_0 = 10^{100}$, such that for any indices $1 \le i,j \le l_0$, $$ (f_i - g_i)(f_j - g_j) > 0. $$ That is, either for all $i$, $f_i > g_i$, or for all $i$, $f_i < g_i$.

Since you cannot output these huge sequences, you only need to tell whether such a pair of extensions exists.

Moreover, to prevent trivial solutions, you will be given $q$ independent queries. In each query, several elements in $X$ and/or $Y$ (based on the original sequences) are modified. For each query, after applying the modifications, determine if there exist two extensions $F$ and $G$ (each of length $10^{100}$) satisfying the above property.

It can be shown that such extensions exist if and only if either
(1) every element of the modified $X$ is less than every element of the modified $Y$, i.e., $$\max(X) < \min(Y),$$ or
(2) every element of the modified $X$ is greater than every element of the modified $Y$, i.e., $$\min(X) > \max(Y).$$

inputFormat

The input begins with two integers $n$ and $m$ ($1 \le n,m \le 10^5$), representing the lengths of sequences $X$ and $Y$, respectively.

The second line contains $n$ integers: $x_1, x_2, \ldots, x_n$.

The third line contains $m$ integers: $y_1, y_2, \ldots, y_m$.

The fourth line contains one integer $q$ ($1 \le q \le 10^5$), the number of queries.

Each query is given as follows (queries are independent, i.e. modifications are applied on the original sequences):

• The first line of the query contains an integer $a$ ($0 \le a \le n$), the number of modifications in $X$.
• Then follow $a$ lines, each containing two integers: index new_value (1-indexed), meaning that $x_{index}$ is changed to new_value.
• The next line contains an integer $b$ ($0 \le b \le m$), the number of modifications in $Y$.
• Then follow $b$ lines, each containing two integers: index new_value (1-indexed), meaning that $y_{index}$ is changed to new_value.

For each query, after applying the modifications to copies of the original arrays, output a single line with either Yes or No.

outputFormat

For each query, print a single line containing Yes if there exist two extensions satisfying the condition, or No otherwise.

sample

3 3
1 2 3
4 5 6
5
0
0
1
2 10
0
0
1
1 0
1
1 10
1
3 5
1
2 0
1
1 5

Yes
No
No
No
Yes

</p>