Ферзі, коні та пішаки
Ви усі ймовірно знайомі зі знаменитою задачею про 8-м ферзів, у якій Вас просять розмістити 8 ферзів на шаховій дошці так, що ніякі два з них не нападають один на одного. У цій задачі вам задані розміщені у деяких місцях ферзі, коні та пішаки і вам необхідно вияснити, скільки вільних клітинок на дошці не знаходяться під атакою як ферзя, так і коня (або обох). Ми будемо називати такі клітинки "безпечними" клітинками. Тут пішаки будуть грати лише роль блокіраторів і не мають можливості нападати на інші клітинки. Дошка, зображена на рисунку нижче, має 6 безпечних клітинок (затемнені клітинки знаходяться у безпеці).
Нагадаємо, що кінь може перейти з поточної позиції на довільну незайняту клітинку, яка знаходиться у пролежному куті прямокутника 2х3, ферзь рухається до довільної клітинки, яка видима у довільному з восьми горизонтальних, вертикальних та діагональних напрямків від поточного положення. Зверніть увагу, що переміщення ферзя може бути заблоковано іншою фігурою, у то час як переміщення коня - не може.
Вхідні дані
Вам будет задано декілька тестів. Кожен тест селадається з 4-х рядків. Перший рядок буде містити два цілих числа n та m, які задають розміри дошки, вказуючи кількість рядків та стовбців відповідно. Жодне число не буде перевищувати 1000. Кожен з наступних трьох рядків буде мати вид
k r_1 c_1 r_2 c_2 ... r_k c_k
з вказуванням кількості та розміщення ферзів, коней та пішаків, відповідно. Нумерація рядків та стовбців починається з одиниці. Кількість кожної з фігур буде не більшою 100. Значення n = m = 0 вказують на завершення вхідних даних.
Вихідні дані
Для кожного тесту необхідно вивести один рядок виду
Board b has s safe squares.
де b - це номер тесту (починаючи з одиниці), а також ви вказуєте правильне значення для s.