eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Забор

Забор

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Для парка культуры и отдыха было решено изготовить забор. Чтобы забор не портил своим невзрачным видом облик города, архитекторы решили сделать забор фигурным, и разработали несколько различных шаблонов для изготовления секций забора. Шаблон представляет собой многоугольник, где три стороны всегда одинаковы, а четвертая сторона (верхняя часть забора) представляет ломаную линию. Проекции вершин этой ломаной линии на основание забора следуют равномерно, и таким образом шаблон описывается как последовательность высот точек. Высота точек указывается в целых миллиметрах и варьируется от 0 до 2047.

Количество точек в шаблоне равняется L (1 <= L <= 10000). Архитекторы разработали M шаблонов (1 <= M <= 10000), и завод изготовил по шаблонам N секций (N <= 10000000). Пример секции с L = 7 изображен на рисунке.

При транспортировке секций забора до парка произошла авария, и готовые секции забора рассыпались и перемешались. При разборе завалов были выполнены измерения секций, и теперь, зная высоты, необходимо определить, к какому шаблону принадлежит каждая секция забора. Кроме того, при падении секции забора могли быть повреждены (например, могли обломаться зубья забора), поэтому необходимо также посчитать случаи, когда извлечённая из завала секция не совпадает ни с одним шаблоном.

Впрочем, дело несколько упрощается – внутренняя (обращённая в парк) сторона секции отличается по цвету от внешней стороны, поэтому можно сказать с уверенностью, что измерения высот секции проделаны в том же порядке, что и в шаблоне.

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

Все данные разделяются одним пробелом. Последние данные в строке завершаются символом перевода строки.

Первая строка содержит количество тестов. Далее идут данные тестов.

Первая строка данных теста содержит значения L (число точек в шаблоне и секции), M (число различных шаблонов), N (число найденных секций).

Далее M строчек содержат информацию о шаблоне: номер шаблона (натуральное число) и L точек шаблона.

Далее N строчек содержат информацию о секциях забора, в каждой строке содержится L точек одной секции забора.

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

В первой строке выводится слово TEST и через пробел номер теста.

Затем следует N строк, каждая строка содержит номер шаблона, с которым совпала секция, либо, если подходящего шаблона не найдено, то выводится символ дефиса '-'.

В последней строке теста выводится слово ”OK=” (без кавычек) и число секций, сопоставленных с шаблонами, через пробел символы ”BAD=” и число испорченных секций.

Пример

Входные данные #1
2
4 2 4
1 250 123 0 66
2 22 31 120 100
250 123 0 66
22 31 120 100
25 31 120 100
250 123 0 66
3 3 4
1 55 11 12
3 33 1 2
2 14 15 2
55 11 12
14 15 2
33 1 2
14 15 2
Выходные данные #1
TEST 1
1
2
-
1
OK=3 BAD=1
TEST 2
1
2
3
2
OK=4 BAD=0