Problem Description

A sequence $B = \{b_1,b_2,\cdots,b_n\}$ is called an extension of another sequence $A = \{a_1,a_2,\cdots,a_m\}$ if and only if there exists a sequence of positive integers $L = \{l_1,l_2,\cdots,l_m\}$ such that, after replacing $a_i$ with $l_i$ copies of $a_i$, we obtain the sequence $B$. For example:

• $\{1,3,3,3,2,2,2\}$ is an extension of $\{1,3,3,2\}$, with $L = \{1,1,2,3\}$ or $\{1,2,1,3\}$.
• However, $\{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\}$.

Little R gives you two sequences $X$ and $Y$. He wants you to find an extension $F = \{f_i\}$ of $X$ with length $l_0 = 10^{100}$ and an extension $G = \{g_i\}$ of $Y$ with length $l_0$, such that for any $1 \le i , j \le l_0$, we have $(f_i - g_i)(f_j - g_j) > 0$. Since the sequences are too long, you only need to tell Little R whether such two sequences exist.

To prevent you from just guessing, Little R also gives $q$ additional queries. In each additional query, Little R will modify the values of some elements in $X$ and $Y$. For each new $X$ and $Y$, you need to make the above decision again.

The queries are independent. In each query, all modifications are applied to the original sequences.

Input Format

The first line contains four integers $c, n, m, q$, representing the test point index, the length of sequence $X$, the length of sequence $Y$, and the number of additional queries. For the samples, $c$ indicates that the sample has the same constraints as test point $c$.

The second line contains $n$ integers $x_1,x_2,\cdots, x_n$, describing sequence $X$.

The third line contains $m$ integers $y_1,y_2,\cdots, y_m$, describing sequence $Y$.

Next, $q$ groups of additional queries are given. For each group:

• The first line contains two integers $k_x$ and $k_y$, representing the numbers of modifications to sequences $X$ and $Y$, respectively.
• The next $k_x$ lines each contain two integers $p_x, v_x$, meaning setting $x_{p_x}$ to $v_x$.
• The next $k_y$ lines each contain two integers $p_y, v_y$, meaning setting $y_{p_y}$ to $v_y$.

Output Format

Output one line containing a 01 sequence of length $(q+1)$. The first element is the answer for the initial query, and the following $q$ elements are the answers for the additional queries in order. For each query, if there exist sequences $F$ and $G$ that satisfy the conditions, output 1; otherwise output 0.

3 3 3 3
8 6 9
1 7 4
1 0
3 0
0 2
1 8
3 5
1 1
2 8
1 7

1001

Hint

[Sample Explanation #1]

Since $F$ and $G$ are too long, we use ellipses to indicate repeating the last element until the sequence length reaches $l_0$. For example, $\{1,2,3,3,\cdots\}$ means that all elements after the third one are $3$.

The following describes four queries in order. The first is the initial query, and the next three are additional queries:

1. $A = \{8,6,9\}$, $B = \{1,7,4\}$. Take $F = \{8,8,6,9,\cdots\}, G = \{1,7,4,4,\cdots\}$.
2. $A = \{8,6,0\}$, $B = \{1,7,4\}$. It can be proven that no solution satisfies the requirement.
3. $A = \{8,6,9\}$, $B = \{8,7,5\}$. It can be proven that no solution satisfies the requirement.
4. $A = \{8,8,9\}$, $B = \{7,7,4\}$. Take $F = \{8,8,9,\cdots\}, G = \{7,7,4,\cdots\}$.

[Sample Explanation #2]

This sample satisfies the constraints of test point $4$.

[Sample Explanation #3]

This sample satisfies the constraints of test point $7$.

[Sample Explanation #4]

This sample satisfies the constraints of test point $9$.

[Sample Explanation #5]

This sample satisfies the constraints of test point $18$.

[Constraints]

For all testdata, it is guaranteed that:

• $1 \le n, m \le 5 \times 10 ^ 5$.
• $0 \le q \le 60$.
• $0 \le x_i, y_i < 10 ^ 9$.
• $0 \le k_x, k_y \le 5 \times 10 ^ 5$, and the sum of $(k_x+k_y)$ over all additional queries does not exceed $5 \times 10 ^ 5$.
• $1 \le p_x \le n$, $1 \le p_y \le m$, $0 \le v_x, v_y < 10 ^ 9$.
• For each additional query, all $p_x$ are pairwise distinct, and all $p_y$ are pairwise distinct.

Special property: For each query (including the initial query and additional queries), it is guaranteed that $x_1 < y_1$, and $x_n$ is the unique minimum value in sequence $X$, while $y_m$ is the unique maximum value in sequence $Y$.

Translated by ChatGPT 5