称某个序列 B = {b1 , b2 , · · · , bn } 是另一个序列 A = {a1 , a2 , · · · , am } 的拓展当且仅 当存在正整数序列 L = {l1 , l2 , · · · , lm }，将 ai 替换为 li 个 ai 后得到序列 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 的一个长度为 l0 = 10100 的拓 展 F = {fi } 以及 Y 的一个长度为 l0 的拓展 G = {gi }，使得任意 1 ≤ i, j ≤ l0 都有 (fi − gi )(fj − gj ) > 0。由于序列太长， 你只需要告诉小 R 是否存在这样的两个序列即可。
为了避免你扔硬币蒙混过关， 小 R 还给了 q 次额外询问， 每次额外询问中小 R 会 修改 X 和 Y 中若干元素的值。你需要对每次得到的新的 X 和 Y 都进行上述的判断。
询问之间是独立的，每次询问中涉及的修改均在原始序列上完成。

输入的第一行包含四个整数 c,n,m, q，分别表示测试点编号、序列 X 的长度、序列 Y 的长度和额外询问的个数。对于样例， c 表示该样例与测试点 c 拥有相同的限制条件。
输入的第二行包含 n 个整数 x1 , x2 , · · · , xn ，描述序列 X。
输入的第三行包含 m 个整数 y1 , y2 , · · · , ym ，描述序列 Y。
接下来依次描述 q 组额外询问。对于每组额外询问：
. 输入的第一行包含两个整数 kx 和 ky ，分别表示对序列 X 和 Y 产生的修改个数。 . 接下来 kx 行每行包含两个整数 px , vx ，表示将 xpx 修改为 vx。
. 接下来 ky 行每行包含两个整数 py , vy ，表示将 ypy 修改为 vy。

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

【样例1解释】
由于 F 和 G 太长，用省略号表示重复最后一个元素直到序列长度为 l0。如 {1, 2, 3, 3, · · · } 表示序列从第三个元素之后都是 3。
以下依次描述四次询问，其中第一次询问为初始询问，之后的三次为额外询问： 1. A = {8, 6, 9}，B = {1, 7, 4}，取 F = {8, 8, 6, 9, · · · }, G = {1, 7, 4, 4, · · · }；

1. A = {8, 6, 0}，B = {1, 7, 4}，可以证明不存在满足要求的方案；
   
2. A = {8, 6, 9}，B = {8, 7, 5}，可以证明不存在满足要求的方案；
   
3. A = {8, 8, 9}，B = {7, 7, 4}，取 F = {8, 8, 9, · · · }, G = {7, 7, 4, · · · }。
   【数据范围】
   对于所有测试数据，保证：
   . 1 ≤ n, m ≤ 5 × 105；
   . 0 ≤ q ≤ 60；
   . 0 ≤ xi , yi < 109；
   . 0 ≤ kx , ky ≤ 5 × 105 ，且所有额外询问的 (kx + ky ) 的和不超过 5 × 105；
   . 1 ≤ px ≤ n ，1 ≤ py ≤ m ，0 ≤ vx , vy < 109；
   对于每组额外询问， px 两两不同， py 两两不同。
   
   特殊性质： 对于每组询问（包括初始询问和额外询问）， 保证 x1 < y1 ，且 xn 是序 列 X 唯一的一个最小值， ym 是序列 Y 唯一的一个最大值。

NOIP