时间限制：1秒　　内存限制：256M

---

【问题描述】

　　称某个序列 \(B={b_1,b_2 ,⋯,b_n }\) 是另一个序列 \(A={a_1 ,a_2 ,⋯,a_m }\) 的拓展当且仅当存在正整数序列 \(L={l_1 ,l_2 ,⋯,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≤i,j≤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,⋯,x_n\)，描述序列 \(X\)。
　　输入的第三行包含 \(m\) 个整数 \(y_1,y_2,⋯,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\)。

【输入输出样例1】

　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,⋯}\) 表示序列从第三个元素之后都是 \(3\)。
　　以下依次描述四次询问，其中第一次询问为初始询问，之后的三次为额外询问：
　　1. \(A={8,6,9}，B={1,7,4}\)，取 \(F={8,8,6,9,⋯},G={1,7,4,4,⋯}\)；
　　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,⋯},G={7,7,4,⋯}\)。

【输入输出样例2】

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

【输入输出样例3】

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

【输入输出样例4】

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

【输入输出样例5】

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

【数据范围】

　　对于所有测试数据，保证：
　　● \(1≤n,m≤5×10^5\)；
　　● \(0≤q≤60\)；
　　● \(0≤x_i,y_i<10^9\)；
　　● \(0≤k_x,k_y≤5×10^5\)，且所有额外询问的 \((k_x+k_y)\) 的和不超过 \(5×10^5\)；
　　● \(1≤p_x≤n，1≤p_y≤m，0≤v_x,v_y<10^9\)；
　　对于每组额外询问，\(p_x\) 两两不同，\(p_y\) 两两不同。

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

【样例数据下载】

　　expand.zip