描述

大家都熟悉著名的 8 皇后问题，它要求在棋盘上放置 8 个皇后，使得任意两个不在同一行、列或对角线。在本题中，给定皇后、骑士和兵的位置，要求统计棋盘上未被任何皇后或骑士（或二者）攻击的空格数量，我们称之为“安全”格子。兵只作为阻挡者，不具有吃子能力。下图中有 6 个安全格（阴影部分）。

回顾：骑士能跳到任何与当前位置构成 2×3 长方形对角的空格；皇后能沿八个方向（水平、垂直、对角）可见地移动。皇后的移动会被其他棋子阻挡，而骑士移动不受阻挡。

输入

有多组测试。每组测试包含 4 行：

1. 第一行有两个整数 $n$ 和 $m$，分别表示棋盘的行数和列数（$\le1000$）。
2. 第二行描述所有皇后位置，格式为：

q r1 c1 r2 c2 ... rq cq

其中 $q$ 是皇后数，后跟每个皇后的行号和列号（均从 1 开始）。 3. 第三行同理描述骑士位置。 4. 第四行同理描述兵的位置。 当 $n=m=0$ 时输入结束，该行不处理。任一棋子种类数量均不超过 100。

输出

每组测试输出一行：

Board b has s safe squares.

其中 $b$ 是棋盘编号（从 1 开始），$s$ 是安全格数量。

输入数据 1

4 4
2 1 4 2 4
1 1 2
1 2 3
2 3
1 1 2
1 1 1
0
1000 1000
1 3 3
0
0
0 0

输出数据 1

Board 1 has 6 safe squares.
Board 2 has 0 safe squares.
Board 3 has 996998 safe squares.

来源

East Central North America 2005