题目描述

称某个序列 $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$。

输入样例

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$ 太长，用省略号表示重复最后一个元素直到序列长度为 $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, · · · \}$。 【数据范围】 对于所有测试数据，保证： • $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$ 两两不同。

测试点编号	n, m ≤	特殊性质
1	1	否
2	2
3, 4	6
5	200
6, 7	2, 000
8, 9	4 × 104	是
10, 11	1.5 × 105
12 ∼ 14	5 × 105
15, 16	4 × 104	否
17, 18	1.5 × 105
19, 20	5 × 105

特殊性质：对于每组询问（包括初始询问和额外询问），保证 $x_1$

公式排版补正

原站将拓展长度指数显示为10100；这里还原为$10^{100}$。这是根据CCF原卷的同源题意、范围与PDF指数提取规律，并与同源公开题面交叉核对后作出的排版还原推断。原始采集文本另存，未更改输入输出协议或数据范围。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共6个测试点，非原站或官方原始数据。总分100分。