D. Кино
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
input.txt
вывод
output.txt

В Берляндии всего m актеров. У каждого актера свой идентификатор — целое число от 1 до m (у разных актеров разные идентификаторы). Вася очень любит смотреть берляндские фильмы с берляндскими актерами, и у него есть k любимых актеров. Мальчик посмотрел анонсы фильмов на следующий месяц и записал про каждый фильм следующую информацию: название фильма, количество актеров, которые в нем снимались, и идентификаторы этих актеров. Причем названия фильмов и количество актеров он переписать успел, а вот идентификаторы некоторых актеров нет. Вася посмотрел на свои записи и задумался: какие же из фильмов станут его любимыми, а какие нет. После того, как Вася узнает точные актерские составы всех фильмов, любимые фильмы будут определяться так: фильм становится любимым фильмом, если ни в каком другом фильме из Васиного списка не играет больше любимых актеров.

Помогите мальчику для каждого фильма определить, что этот фильм:

  • точно будет любимым фильмом,
  • точно не будет любимым фильмом,
  • может как быть любимым, так и не быть.
Входные данные

В первой строке входного файла записаны два целых числа m и k (1 ≤ m ≤ 100, 1 ≤ k ≤ m) — количество актеров в Берляндии и количество любимых актеров Васи.

Во второй строке содержатся k различных целых чисел ai (1 ≤ ai ≤ m) — идентификаторы любимых актеров Васи.

В третьей строке содержится единственное целое число n (1 ≤ n ≤ 100) — количество фильмов в Васином списке.

Далее следует n блоков строк, в каждом из которых содержится описание очередного фильма. Описание i-го фильма содержит 3 строки:

  • в первой из них содержится строка si (si состоит из маленьких латинских букв и может иметь длину от 1 до 10 символов включительно) — название фильма,
  • во второй — целое неотрицательное число di (1 ≤ di ≤ m) — количество актеров, играющих в этом фильме,
  • в третьей — di целых чисел bi, j (0 ≤ bi, j ≤ m) — идентификаторы актеров, играющих в этом фильме. Если bi, j = 0, то это значит, что Вася не помнит идентификатор j-го актера. Гарантируется, что в перечне актеров для одного фильма не встречается двух одинаковых.

Названия всех фильмов различны. Числа в строках разделяются одиночными пробелами.

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

В выходной файл выведите n строк. В i-ой строке выведите:

  • 0, если i-ый фильм точно будет любимым,
  • 1, если i-ый фильм точно будет нелюбимым,
  • 2, если i-ый фильм может быть как любимым, так и нелюбимым.
Примеры
Входные данные
5 3
1 2 3
6
firstfilm
3
0 0 0
secondfilm
4
0 0 4 5
thirdfilm
1
2
fourthfilm
1
5
fifthfilm
1
4
sixthfilm
2
1 0
Выходные данные
2
2
1
1
1
2
Входные данные
5 3
1 3 5
4
jumanji
3
0 0 0
theeagle
5
1 2 3 4 0
matrix
3
2 4 0
sourcecode
2
2 4
Выходные данные
2
0
1
1
Примечание

Пояснение ко второму примеру:

  • В фильме jumanji теоретически может играть от 1 до 3 любимых Васей актеров.
  • В фильме theeagle играют все три любимых актера, поскольку актер, которого Вася не запомнил, может иметь только идентификатор 5.
  • В фильме matrix может играть только один любимый актер.
  • В фильме sourcecode не играет никто из любимых актеров.

Таким образом, фильм theeagle — точно любимый, фильмы matrix и sourcecode — точно нелюбимые, а фильм jumanji может являться как любимым (если в нем играют все три любимых актера), так и нелюбимым.