Олимпиадный тренинг

Задача . C. Подготовка к экзамену

Задача

Монокарп готовится к своему первому экзамену в университете. Программа экзамена состоит из \(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, если Монокарп не сдаст.

Примечание

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

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

Примеры

№	Входные данные	Выходные данные
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	0100 0000 1111 10

time 1500 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	3

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет