Preparing for the Exam
Contest: Codeforces Round 995 (Div. 3)
Difficulty rating: 1000
Tags: constructive algorithms, implementation

Monocarp is preparing for his first exam at the university. There are $$$n$$$ different questions which can be asked during the exam, numbered from $$$1$$$ to $$$n$$$. There are $$$m$$$ different lists of questions; each list consists of exactly $$$n-1$$$ different questions. Each list $$$i$$$ is characterized by one integer $$$a_i$$$, which is the index of the only question which is not present in the $$$i$$$-th list. For example, if $$$n = 4$$$ and $$$a_i = 3$$$, the $$$i$$$-th list contains questions $$$[1, 2, 4]$$$.

During the exam, Monocarp will receive one of these $$$m$$$ lists of questions. Then, the professor will make Monocarp answer all questions from the list. So, Monocarp will pass only if he knows all questions from the list.

Monocarp knows the answers for $$$k$$$ questions $$$q_1, q_2, \dots, q_k$$$. For each list, determine if Monocarp will pass the exam if he receives that list.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

Each test case consists of three lines:

- the first line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$2 \le n \le 3 \cdot 10^5$$$; $$$1 \le m, k \le n$$$);
- the second line contains $$$m$$$ distinct integers $$$a_1, a_2, \dots, a_m$$$ ($$$1 \le a_i \le n$$$; $$$a_i < a_{i+1}$$$);
- the third line contains $$$k$$$ distinct integers $$$q_1, q_2, \dots, q_k$$$ ($$$1 \le q_i \le n$$$; $$$q_i < q_{i+1}$$$).

Additional constraints on the input:

- the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output format:
For each test case, print a string of $$$m$$$ characters. The $$$i$$$-th character should be 1 if Monocarp passes the exam if he receives the $$$i$$$-th question list, 0 if Monocarp won't pass.

Constraints:
Time limit: 1.5 s
Memory limit: 256.0 MB

Note:
In the first test case, Monocarp knows the questions $$$[1, 3, 4]$$$. Let's consider all the question lists:

- the first list consists of questions $$$[2, 3, 4]$$$. Monocarp doesn't know the $$$2$$$-nd question, so he won't pass;
- the second list consists of questions $$$[1, 3, 4]$$$. Monocarp knows all these questions, so he will pass;
- the third list consists of questions $$$[1, 2, 4]$$$. Monocarp doesn't know the $$$2$$$-nd question, so he won't pass;
- the fourth list consists of questions $$$[1, 2, 3]$$$. Monocarp doesn't know the $$$2$$$-nd question, so he won't pass.

Example input:
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

Example output:
0100
0000
1111
10

Editorial:
For every question list, we should check if Monocarp knows all questions from the list, i. e. all numbers $$$1, 2, \dots, a_{i-1}, a_{i+1}, \dots, n$$$ appear in the list $$$[q_1, q_2, \dots, q_k]$$$. Searching for every number in the list $$$q$$$ naively is too slow; instead, we can make a boolean array such that the $$$j$$$-th element in it is true if and only if Monocarp knows the $$$j$$$-th question. That way, we can check if an integer appears in the list $$$q$$$ in $$$O(1)$$$.
However, that is not enough, since every list of questions contains $$$O(n)$$$ questions, and there are $$$O(n)$$$ lists. We need to use the fact that every list contains exactly $$$n-1$$$ questions somehow.
If Monocarp knows all $$$n$$$ questions, he can answer any question list (since he knows everything). If Monocarp knows $$$n-2$$$ questions or less, he cannot pass at all, since every question list contains more questions than he knows. The only case that's left if when $$$k=n-1$$$, i. e. Monocarp knows all questions except for one. Let's analyze it in more detail (the two next paragraphs will assume that $$$k=n-1$$$).
Since every question list has the same size as the set of questions known by Monocarp, then in order for Monocarp to pass the exam, these two sets of questions must be equal. However, checking that they are equal by iterating on their contents is too slow; instead, we will check that two sets of questions are different by using the elements which are absent from them.
Let's check if Monocarp knows the question $$$a_i$$$. If he does, then the $$$i$$$-th list of questions is different from the set of questions he knows, so he can't pass. But if Monocarp doesn't know the $$$a_i$$$-th question, then he knows every question which is not $$$a_i$$$, so he can pass. So, Monocarp knows the $$$i$$$-th question list if and only if he does not know the $$$a_i$$$-th question, and this can be checked in $$$O(1)$$$.
This way, we get a solution working in $$$O(n)$$$ on each test case.