称某个序列 $B=\{b_1,b_2,\cdots ,b_n\}$ 是另一个序列 $A=\{a_1,a_2,\cdots ,a_m\}$ 的拓展当且仅当存在正整数序列 $L=\{l_1,l_2,\cdots ,l_m\}$，将 $a_i$ 替换为 $l_i$ 个 $a_i$ 后得到序列 $B$。例如，

• $\{1,3,3,3,2,2,2\}$ 是 $\{1,3,3,2\}$ 的拓展，取 $L=\{1,1,2,3\}$ 或 $\{1,2,1,3\}$；
• 而 $\{1,3,3,2\}$ 不是 $\{1,3,3,3,2\}$ 的拓展，$\{1,2,3\}$ 不是 $\{1,3,2\}$ 的拓展。

小 R 给了你两个序列 $X$ 和 $Y$，他希望你找到 $X$ 的一个长度为 $l_0={10}^{100}$ 的拓展 $F=\{f_i\}$ 以及 $Y$ 的一个长度为 $l_0$ 的拓展 $G=\{g_i\}$，使得任意 $1\le i,j\le l_0$ 都有 $(f_i-g_i)(f_j-g_j)>0$。由于序列太长，你只需要告诉小 R 是否存在这样的两个序列即可。

为了避免你扔硬币蒙混过关，小 R 还给了 $q$ 次额外询问，每次额外询问中小 R 会修改 $X$ 和 $Y$ 中若干元素的值。你需要对每次得到的新的 $X$ 和 $Y$ 都进行上述的判断。

询问之间是独立的，每次询问中涉及的修改均在原始序列上完成。

输入格式

输入的第一行包含四个整数 $c,n,m,q$，分别表示测试点编号、序列 $X$ 的长度、序列 $Y$ 的长度和额外询问的个数。对于样例，$c$ 表示该样例与测试点 $c$ 拥有相同的限制条件。

输入的第二行包含 $n$ 个整数 $x_1,x_2,\cdots ,x_n$，描述序列 $X$。

输入的第三行包含 $m$ 个整数 $y_1,y_2,\cdots ,y_m$，描述序列 $Y$。

接下来依次描述 $q$ 组额外询问。对于每组额外询问：

• 输入的第一行包含两个整数 $k_x$ 和 $k_y$，分别表示对序列 $X$ 和 $Y$ 产生的修改个数。
• 接下来 $k_x$ 行每行包含两个整数 $p_x,v_x$，表示将 $x_{p_x}$ 修改为 $v_x$。
• 接下来 $k_y$ 行每行包含两个整数 $p_y,v_y$，表示将 $y_{p_y}$ 修改为 $v_y$。

输出格式

输出一行，其中包含一个长度为 $(q+1)$ 的 01 序列，序列的第一个元素表示初始询问的答案，之后 $q$ 个元素依次表示每组额外询问的答案。对于每个询问，如果存在满足题目条件的序列 $F$ 和 $G$，输出 1，否则输出 0。

样例一

input

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

output

1001

提示

【样例解释 #1】

由于 $F$ 和 $G$ 太长，用省略号表示重复最后一个元素直到序列长度为 $l_0$。如 $\{1,2,3,3,\cdots \}$ 表示序列从第三个元素之后都是 $3$。

以下依次描述四次询问，其中第一次询问为初始询问，之后的三次为额外询问：

1. $A=\{8,6,9\}$，$B=\{1,7,4\}$，取 $F=\{8,8,6,9,\cdots \},G=\{1,7,4,4,\cdots \}$；
2. $A=\{8,6,0\}$，$B=\{1,7,4\}$，可以证明不存在满足要求的方案；
3. $A=\{8,6,9\}$，$B=\{8,7,5\}$，可以证明不存在满足要求的方案；
4. $A=\{8,8,9\}$，$B=\{7,7,4\}$，取 $F=\{8,8,9,\cdots \},G=\{7,7,4,\cdots \}$。

【样例解释 #2】

该组样例满足测试点 $4$ 的条件。

【样例解释 #3】

该组样例满足测试点 $7$ 的条件。

【样例解释 #4】

该组样例满足测试点 $9$ 的条件。

【样例解释 #5】

该组样例满足测试点 $18$ 的条件。

【数据范围】

对于所有测试数据，保证：

• $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$，且所有额外询问的 $(k_x+k_y)$ 的和不超过 $5\times {10}^5$；
• $1\le p_x\le n$，$1\le p_y\le m$，$0\le v_x,v_y<{10}^9$；
• 对于每组额外询问，$p_x$ 两两不同，$p_y$ 两两不同。

特殊性质：对于每组询问（包括初始询问和额外询问），保证 $x_1<y_1$，且 $x_n$ 是序列 $X$ 唯一的一个最小值，$y_m$ 是序列 $Y$ 唯一的一个最大值。

时间限制：$\mathtt{\text{1s}}$

空间限制：$\mathtt{\text{512MB}}$