← 返回题目列表

Codeforces · 2051/C

C. 准备考试

中文机器翻译题面 查看原题

Monocarp 正在准备他在大学的第一次考试。考试期间可以提出 $$$n$$$ 不同的问题,编号从 $$$1$$$ 到 $$$n$$$。有 $$$m$$$ 不同的问题列表;每个列表均包含 $$$n-1$$$ 不同的问题。每个列表 $$$i$$$ 都由一个整数 $$$a_i$$$ 表征,它是第 $$$i$$$ 列表中不存在的唯一问题的索引。例如,如果 $$$n = 4$$$ 且 $$$a_i = 3$$$,则第 $$$i$$$ 列表包含问题 $$$[1, 2, 4]$$$。

在考试期间,Monocarp 将收到以下 $$$m$$$ 问题列表之一。然后,教授会让Monocarp回答列表中的所有问题。因此,只有当 Monocarp 知道列表中的所有问题时,他才会通过。

Monocarp 知道 $$$k$$$ 问题 $$$q_1、q_2、\dots、q_k$$$ 的答案。对于每个列表,确定 Monocarp 收到该列表后是否会通过考试。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例由三行组成:

- 第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$2 \le n \le 3 \cdot 10^5$$$; $$$1 \le m, k \le n$$$);
- 第二行包含 $$$m$$$ 不同的整数 $$$a_1, a_2, \dots, a_m$$$ ($$$1 \le a_i \le n$$$; $$$a_i < a_{i+1}$$$);
- 第三行包含 $$$k$$$ 不同的整数 $$$q_1, q_2, \dots, q_k$$$ ($$$1 \le q_i \le n$$$; $$$q_i < q_{i+1}$$$)。

输入的附加限制:

- 所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。

输出

对于每个测试用例,打印 $$$m$$$ 字符的字符串。如果 Monocarp 收到第 $$$i$$$ 问题列表,则如果 Monocarp 通过考试,则第 $$$i$$$ 个字符应为 1;如果 Monocarp 未通过,则第 $$$i$$$ 个字符应为 0。

示例

输入 #1

4
4 4 3
1 2 3 4
1 3 4
5 4 3
1 2 3 4
1 3 4
4 4 4
1 2 3 4
1 2 3 4
2 2 1
1 2
2

输出 #1

0100
0000
1111
10

注意

在第一个测试用例中,Monocarp 知道问题 $$$[1, 3, 4]$$$。让我们考虑一下所有问题列表:

- 第一个列表包含问题 $$$[2, 3, 4]$$$。 Monocarp 不知道 $$$2$$$-nd 问题,所以他不会通过;
- 第二个列表包含问题 $$$[1, 3, 4]$$$。 Monocarp知道所有这些问题,所以他会通过;
- 第三个列表包含问题 $$$[1, 2, 4]$$$。 Monocarp 不知道 $$$2$$$-nd 问题,所以他不会通过;
- 第四个列表包含问题 $$$[1, 2, 3]$$$。 Monocarp 不知道 $$$2$$$-nd 问题,所以他不会通过。