称某个序列 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。
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
【样例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, · · · };
NOIP