Задача №3900. Система защиты
«ПермьОлимпБанк» разработал сверхнадежную систему защиты ценных бумаг. В правом верхнем углу любой бумаги должно присутствовать прямоугольное изображение в виде черно-белого рисунка. Для определения подлинности документов была создана библиотека контрольных элементов. Если документ подлинный, то в изображении на документе заданное количество раз присутствует каждый контрольный элемент из библиотеки. В библиотеке нет совпадающих элементов.
Система контроля после сканирования получает изображение в виде цифрового массива N × M, в котором цифра 1 соответствует черному цвету, а цифра 0 — белому. Затем система ищет контрольные элементы в полученном массиве.
Контрольный элемент представляется массивом размером L × L цифр, каждая из которых равна 0 или 1. В библиотеке — K контрольных элементов. Элемент библиотеки должен точно совпадать с какой-либо частью изображения. При сравнении изображения и контрольных элементов повороты не допускаются.
Требуется определить, сколько раз каждый элемент библиотеки встречается в изображении, описанном во входном файле.
В первой строке входных данных записаны через пробел числа N, M, K, L (N ≤ 100 000, M ≤ 1 000, L ≤ 50, K ≤ 20).
Далее следуют по порядку К блоков, соответствующих элементам контрольного образца в библиотеке. Каждый блок состоит из L строк по L цифр (ноль или единица). После каждого блока следует пустая строка.
В последующих N строках записаны по M цифр в каждой, соответствующих изображению.
Выходной файл должны состоять из К строк.
В каждой строке содержится два числа: номер контрольного элемента из библиотеки и число его обнаружений (0 — если элемент не обнаружен).
Номер контрольного элемента из библиотеки в первой строке равен 1, во второй — 2 и т.д. Все числа в строках должны быть разделены пробелом.
Каждый тест оценивается независимо от других.
10 10 2 3 010 111 010 100 011 001 0010010010 0100001111 0000000100 0000100000 0001111000 0000101000 0100000010 0001000110 0011111000 0101000000
1 2 2 1