A sequence $B = \{b_1, b_2, \dots, b_n\}$ is called an expansion of another sequence $A = \{a_1, a_2, \dots, a_m\}$ if and only if there exists a sequence of positive integers $L = \{l_1, l_2, \dots, l_m\}$ such that $B$ is obtained by replacing each $a_i$ with $l_i$ copies of $a_i$. For example: $\{1, 3, 3, 3, 2, 2, 2\}$ is an expansion of $\{1, 3, 3, 2\}$, with $L = \{1, 1, 2, 3\}$ or $\{1, 2, 1, 3\}$; $\{1, 3, 3, 2\}$ is not an expansion of $\{1, 3, 3, 3, 2\}$, and $\{1, 2, 3\}$ is not an expansion of $\{1, 3, 2\}$.

You are given two sequences $X$ and $Y$. You need to find an expansion $F = \{f_i\}$ of $X$ with length $l_0 = 10^{100}$ and an expansion $G = \{g_i\}$ of $Y$ with length $l_0$, such that for any $1 \le i, j \le l_0$, $(f_i - g_i)(f_j - g_j) > 0$. Since the sequences are very long, you only need to tell whether such two sequences exist.

To prevent guessing, you are given $q$ additional queries. In each query, some elements of $X$ and $Y$ are modified. You need to perform the aforementioned check for the new $X$ and $Y$ after each query. Queries are independent, and all modifications in each query are performed on the original sequences.

Input

The input is read from the file expand.in.

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

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

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

The following lines describe $q$ additional queries. For each query: The first line contains two integers $k_x$ and $k_y$, representing the number of modifications to sequence $X$ and $Y$, respectively. The next $k_x$ lines each contain two integers $p_x, v_x$, meaning $x_{p_x}$ is changed to $v_x$. * The next $k_y$ lines each contain two integers $p_y, v_y$, meaning $y_{p_y}$ is changed to $v_y$.

Output

The output is written to the file expand.out.

Output a single line containing a 01 sequence of length $(q + 1)$. The first element represents the answer to the initial query, and the subsequent $q$ elements represent the answers to each additional query in order. For each query, output 1 if there exist sequences $F$ and $G$ satisfying the conditions, otherwise output 0.

Constraints

For all test data, 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 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 query, all $p_x$ are distinct, and all $p_y$ are distinct.

Special Property: For every query (including the initial one), it is guaranteed that $x_1 < y_1$, $x_n$ is the unique minimum value of sequence $X$, and $y_m$ is the unique maximum value of sequence $Y$.

Examples

Input 1

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

Output 1

1001

Note 1

Since $F$ and $G$ are too long, ellipses are used to denote repeating the last element until the sequence length reaches $l_0$. For example, $\{1, 2, 3, 3, \dots\}$ indicates that all elements after the third one are 3.

The four queries are described as follows, where the first is the initial query and the subsequent three are additional queries: 1. $A = \{8, 6, 9\}$, $B = \{1, 7, 4\}$, take $F = \{8, 8, 6, 9, \dots\}, G = \{1, 7, 4, 4, \dots\}$; 2. $A = \{8, 6, 0\}$, $B = \{1, 7, 4\}$, it can be proven that no such solution exists; 3. $A = \{8, 6, 9\}$, $B = \{8, 7, 5\}$, it can be proven that no such solution exists; 4. $A = \{8, 8, 9\}$, $B = \{7, 7, 4\}$, take $F = \{8, 8, 9, \dots\}, G = \{7, 7, 4, \dots\}$.