C. Подготовка к экзамену
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Монокарп готовится к своему первому экзамену в университете. Программа экзамена состоит из $$$n$$$ вопросов, пронумерованных от $$$1$$$ до $$$n$$$. На экзамене Монокарпу попадется один из $$$m$$$ различных билетов; каждый билет состоит из ровно $$$n-1$$$ различных вопросов. Каждый билет $$$i$$$ характеризуется одним числом $$$a_i$$$, которое является индексом единственного вопроса, который отсутствует в $$$i$$$-м билете. Например, если $$$n = 4$$$ и $$$a_i = 3$$$, то $$$i$$$-й билет содержит вопросы $$$[1, 2, 4]$$$.

Во время экзамена Монокарп получит один из этих $$$m$$$ билетов. Затем профессор заставит Монокарпа ответить на все вопросы из билета. Таким образом, Монокарп сдаст экзамен только в том случае, если он знает все вопросы из билета.

Монокарп знает ответы на $$$k$$$ вопросов $$$q_1, q_2, \dots, q_k$$$. Для каждого билета определите, сдаст ли Монокарп экзамен, если он получит этот билет.

Входные данные

Первая строка содержит одно целое число $$$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$$$ символов. $$$i$$$-й символ должен быть 1, если Монокарп сдаст экзамен, если он получит $$$i$$$-й билет, или 0, если Монокарп не сдаст.

Пример
Входные данные
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
Выходные данные
0100
0000
1111
10
Примечание

В первом наборе входных данных Монокарп знает вопросы $$$[1, 3, 4]$$$. Рассмотрим все билеты:

  • первый билет состоит из вопросов $$$[2, 3, 4]$$$. Монокарп не знает $$$2$$$-й вопрос, поэтому он не сдаст;
  • второй билет состоит из вопросов $$$[1, 3, 4]$$$. Монокарп знает все эти вопросы, поэтому он сдаст;
  • третий билет состоит из вопросов $$$[1, 2, 4]$$$. Монокарп не знает $$$2$$$-й вопрос, поэтому он не сдаст;
  • четвертый билет состоит из вопросов $$$[1, 2, 3]$$$. Монокарп не знает $$$2$$$-й вопрос, поэтому он не сдаст.