C. 双序列扩展
time limit per test
1.5 с
memory limit per test
512 megabytes
input
expand.in
output
expand.out

称某个序列 $$$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) \gt 0$$$。由于序列太长，你只需要告诉小 R 是否存在这样的两个序列即可。 为了避免你扔硬币蒙混过关，小 R 还给了 $$$q$$$ 次额外询问，每次额外询问中小 R 会修改 $$$X$$$ 和 $$$Y$$$ 中若干元素的值。你需要对每次得到的新的 $$$X$$$ 和 $$$Y$$$ 都进行上述的判断。 询问之间是独立的，每次询问中涉及的修改均在原始序列上完成。
Input

输入的第一行包含四个整数 $$$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$$$。
Output

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

Example
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
Note

【样例解释 #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\}$$$。

【数据范围】

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

  • $$$1 \le n, m \le 5 \times 10 ^ 5$$$；
  • $$$0 \le q \le 60$$$；
  • $$$0 \le x_i, y_i \lt 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 \lt 10 ^ 9$$$；
  • 对于每组额外询问，$$$p_x$$$ 两两不同，$$$p_y$$$ 两两不同。