Вы все вероятно знакомы с знаменитой задачей о 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.