Ферзі, коні та пішаки#3456

Ферзі, коні та пішаки

1 секунда

64 мегабайти

Середня

Мабуть, усі ви знайомі з відомою задачею про $8$ ферзів, у якій потрібно розставити $8$ ферзів на шахівниці так, щоб жодні два ферзі не били один одного. У цій задачі вам дається кілька ферзів, коней і пішаків, уже розташованих на певних клітинках, і потрібно визначити, скільки вільних клітин на дошці не атакуються ані ферзем, ані конем (або обома). Такі клітинки ми назвемо "безпечними". На дошці, показаній на малюнку нижче, є $6$ безпечних клітин (заштриховані клітинки є безпечними).

Нагадаємо, що кінь може перейти зі свого поточного положення на будь-яку вільну клітинку, яка знаходиться у протилежному куті прямокутника розміром $2 \times 3$ 2 \times 3; ферзь може перейти на будь-яку клітинку, що видима по одній із восьми горизонтальних, вертикальних чи діагональних ліній від свого положення. Зверніть увагу, що хід ферзя може бути заблокований іншою фігурою, тоді як хід коня заблокувати неможливо.

Вхідні дані

Вам буде надано кілька тестів. Кожен тест складається з $4$ рядків. Перший рядок містить два цілі числа $n$ і $m$ , які задають розмір дошки — кількість рядків і стовпців відповідно. Жодне з чисел не перевищуватиме $1000$ . Кожен із наступних трьох рядків має вигляд

$k r_{1} c_{1} r_{2} c_{2} \dots r_{k} c_{k}$ k~r_1~c_1~r_2~c_2~\ldots~r_k~c_k

і задає кількість та позиції ферзів, коней та пішаків відповідно. Нумерація рядків і стовпців починається з одиниці. Кількість кожної фігури не перевищуватиме $100$ . Значення $n = m = 0$ n = m = 0 означає кінець вводу.

Вихідні дані

Для кожного тесту слід вивести єдиний рядок у форматі

Board $b$ has $s$ safe squares.

де $b$ — номер тесту (починаючи з одиниці), а $s$ — правильно знайдена кількість безпечних клітин.

Приклади

Приклад 1