COETEST5

Trên một bàn cờ luôn có những ô an toàn mà sẽ không bị những quân cờ khác đánh tới, để an toàn trong nước đi kế tiếp, bạn hãy viết chương trình đếm những ô còn an toàn trên bàn cờ.

Trong bài toán này, bạn sẽ được cung cấp vị trí của quân hậu, quân mã và quân tốt và được yêu cầu tìm xem có bao nhiêu ô trống trên bàn cờ không bị quân hậu hoặc quân mã (hoặc cả hai) tấn công. Chúng tôi sẽ gọi những hình vuông như vậy là những hình vuông “an toàn”. Ở đây, những con tốt sẽ chỉ đóng vai trò là quân chặn và không có khả năng bắt quân.

Ở ví dụ bên dưới, K được ký hiệu là quân mã, Q là quân hậu và P là quân tốt.

Một quân mã có thể di chuyển đến bất kỳ ô trống nào nằm ở góc đối diện của hình chữ nhật 2x3 so với vị trí hiện tại của nó

Quân hậu có thể di chuyển đến bất kỳ ô vuông nào có thể nhìn thấy theo bất kỳ hướng nào trong tám hướng ngang, dọc và chéo từ vị trí hiện tại.

Lưu ý rằng chuyển động của quân hậu có thể bị chặn bởi quân khác, trong khi chuyển động của quân mã thì không.

Dựa trên cách di chuyển của từng loại quân theo như mô tả bên trên, chúng ta có 6 ô vuông an toàn. (Các ô vuông được tô bóng là an toàn.)

Input

Mỗi test case sẽ gồm 4 dòng.

Dòng đầu tiên sẽ chứa hai số nguyên N và M, tương ứng với số hàng và số cột của bàn cờ (0 <= N,M <= 1000).

Ba dòng tiếp theo mỗi dòng sẽ có dạng:

k r1 c1 r2 c2 · · · rk ck

Mỗi dòng sẽ lần lượt chỉ ra vị trí của các quân hậu, quân mã và quân tốt.

Việc đánh số các hàng và cột sẽ bắt đầu từ 1.

Mỗi loại quân sẽ không có nhiều hơn 100.

Các giá trị của n = m = 0 cho biết kết thúc đầu vào.

Output

Mỗi trường hợp thử nghiệm sẽ in ra một dòng theo mẫu sau:

Board tc has s safe squares.

Trong đó: tc là số thứ tự của test case bắt đầu tính từ 1 và số ô an toàn s.

Example

Input:
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

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