#2042. 「NOIP 2023」双序列拓展

称某个序列 是另一个序列 的拓展当且仅当存在正整数序列 ，将 替换为 个 后得到序列 。例如，

• 是 的拓展，取 或 ；
• 而 不是 的拓展， 不是 的拓展。

小 R 给了你两个序列 和 ，他希望你找到 的一个长度为 的拓展 以及 的一个长度为 的拓展 ，使得任意 都有 。由于序列太长，你只需要告诉小 R 是否存在这样的两个序列即可。

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

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

从文件 expand.in 中读入数据。

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

输入的第二行包含 个整数 ，描述序列 。

输入的第三行包含 个整数 ，描述序列 。

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

• 输入的第一行包含两个整数 和 ，分别表示对序列 和 产生的修改个数。
• 接下来 行每行包含两个整数 ，表示将 修改为 。
• 接下来 行每行包含两个整数 ，表示将 修改为 。

输出到文件 expand.out 中。

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

样例 1 输入

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

样例 1 输出

1001

样例 1 解释

由于 和 太长，用省略号表示重复最后一个元素直到序列长度为 。如 表示序列从第三个元素之后都是 。

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

1. ，，取 ；
2. ，，可以证明不存在满足要求的方案；
3. ，，可以证明不存在满足要求的方案；
4. ，，取 。

样例 2

见附加文件中的 expand/expand2.in 和 expand/expand2.ans。

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

样例 3

见附加文件中的 expand/expand3.in 和 expand/expand3.ans。

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

样例 4

见附加文件中的 expand/expand4.in 和 expand/expand4.ans。

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

样例 5

见附加文件中的 expand/expand5.in 和 expand/expand5.ans。

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

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

• ；
• ；
• ；
• ，且所有额外询问的 的和不超过 ；
• ，，；
• 对于每组额外询问， 两两不同， 两两不同。

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