Де Воллі
Чи знайомі ви з відомою серією дитячих книг під назвою "Де Воллі"? У кожній з цих книг є ілюстрації з сотнями людей, і читачам пропонується знайти серед них Воллі.
Ми можемо розглядати "Де Воллі" як задачу зіставлення двовимірних графічних шаблонів. Потрібно знайти фігуру Воллі на зображенні. Було б цікаво створити комп'ютерну програму для вирішення цієї задачі, але це не просто, оскільки Воллі може трохи змінювати свій вигляд на різних зображеннях. Ми вирішили спростити цю задачу, щоб зробити її легшою для розв'язання. Вам пропонується вирішити спрощену версію задачі зіставлення графічних шаблонів.
Дано зображення та шаблон. Обидва представлені у вигляді прямокутних матриць бітів (шаблон завжди квадратний). 0 означає білий колір, а 1 — чорний. Завдання полягає в тому, щоб підрахувати кількість разів, коли шаблон з'являється на зображенні, тобто кількість квадратів на зображенні, які точно відповідають шаблону. Також враховуються шаблони, що з'являються повернутими на будь-які кратні 90 градусів і/або перевернутими, утворюючи дзеркальне відображення.
Вхідні дані
Вхідні дані складаються з кількох наборів даних у такому форматі.
w h p дані зображення дані шаблону
Перша строка кожного набору даних містить три додатні цілі числа w, h та p. w — це ширина зображення, а h — висота зображення, обидва вимірюються в бітах. p — це ширина і висота шаблону, який завжди є квадратним. Ви можете припустити, що 1 ≤ w ≤ 1000, 1 ≤ h ≤ 1000, та 1 ≤ p ≤ 100.
Наступні h рядків представляють зображення. Кожен рядок складається з w/6 (що дорівнює (w+5)/6) символів і відповідає горизонтальному рядку зображення. Кожен з цих символів представляє шість бітів на рядку зображення, зліва направо, у форматі кодування BASE64. Правило кодування наведено в таблиці нижче. Найзначніший біт значення в таблиці відповідає лівому біту на зображенні. Останній символ може також представляти кілька бітів за межами ширини зображення; ці біти слід ігнорувати.
Останні p рядків представляють шаблон. Кожен рядок складається з p/6 символів і закодований так само, як і зображення.
Рядок, що містить три нулі, вказує на кінець введення. Загальний розмір введення не перевищує двох мегабайт.
Вихідні дані
Для кожного набору даних у введенні виведіть один рядок, що містить кількість відповідних квадратів на зображенні. Вихідний рядок не повинен містити зайвих символів.
Два або більше відповідних квадрати можуть перекриватися. У такому випадку вони враховуються окремо. Однак, один квадрат ніколи не враховується двічі або більше, навіть якщо він відповідає як оригінальному шаблону, так і його обертанню, наприклад.