Mario đã cứu được công chúa. Trước mặt họ là một hồ lớn dạng lưới \(n \times m\) ô vuông (đánh số hàng từ \(1\) đến \(n\), cột từ \(1\) đến \(m\)). Trên một số ô có cọc và các ô còn lại là nước. Hồ nước thoả mãn rằng với mọi ô nước \((x, y)\), tồn tại ít nhất một cọc ở một trong các ô \((x + 1, y + 1)\); \((x + 1, y - 1)\); \((x - 1, y + 1)\); \((x - 1, y - 1)\). Mỗi cọc mang một trong hai màu trắng hoặc đen.

Biết rằng Mario đang đứng trên cọc tại ô \((1, 1)\) và công chúa đang đứng trên cọc tại ô \((1, 2)\). Từ ô \((x, y)\) có cọc, nhân vật có thể nhảy qua \(1\) ô có cọc khác ở các vị trí: \((x + 2, y)\); \((x - 2, y)\); \((x, y + 2)\); \((x, y - 2)\); \((x + 2, y + 2)\); \((x + 2, y - 2)\); \((x - 2, y + 2)\); \((x - 2, y - 2)\).

Hai nhân vật có nhiệm vụ thăm tất cả các cọc hiện có trên hồ (mỗi cọc được ghé thăm bởi ít nhất một người). Biết rằng với dữ liệu đầu vào, việc thăm hết các cọc là khả thi.

Khi nhiệm vụ hoàn tất, tất cả các ô nước sẽ mọc lên các cọc, biến cả hồ thành bình địa \(n \times m\) toàn cọc, sẵn sàng cho lễ cưới. Các cọc vừa mọc lên đều chưa có màu; Mario sẽ tô màu trắng hoặc đen cho chúng. Các cọc đã có màu ban đầu phải được giữ nguyên.

Yêu cầu: Công chúa có \(q\) khu vực yêu thích, mỗi khu vực là một hình vuông \(2 \times 2\) xác định bởi tọa độ góc trên–trái \((r_i, c_i)\) (\(1 \le r_i < n\), \(1 \le c_i < m\)). Với mỗi khu vực \(2 \times 2\) này, không được phép tô toàn đen, toàn trắng, hoặc đan xen kiểu bàn cờ vua (hai màu xen kẽ theo ô chéo). Hãy giúp Mario tìm một phương án tô màu hợp lệ cho các cọc sau khi chúng mọc lên. Nếu có nhiều đáp án, in ra bất kỳ đáp án nào.

Input

• Dòng đầu chứa hai số nguyên \(n, m\) (\(2 \le n, m \le 1000\)).

• Mỗi dòng trong số \(n\) dòng tiếp theo chứa một xâu \(m\) ký tự mô tả trạng thái ban đầu của hồ:

  • . — ô nước (chưa có cọc).
  • W — ô có cọc màu trắng.
  • B — ô có cọc màu đen.

  Bảo đảm ô \((1, 1)\) và \((1, 2)\) là ký tự W hoặc B.

• Dòng tiếp theo chứa số nguyên \(q\) (\(0 \le q \le (n - 1)(m - 1)\)).

• Mỗi dòng trong số \(q\) dòng tiếp theo chứa hai số nguyên \(r_i, c_i\) là tọa độ góc trên–trái của một khu vực \(2 \times 2\) yêu thích (\(1 \le r_i < n\), \(1 \le c_i < m\)).

Output

• In ra \(n\) dòng, mỗi dòng là một xâu \(m\) ký tự gồm W hoặc B, biểu diễn phương án tô màu cuối cùng.
• Nếu không tồn tại cách tô màu thoả mãn, in ra -1.

Example

3 2
WB
..
BW
2
2 1
1 1

WB
WW
BW

Scoring

• Subtask \(1\) (\(10\) điểm): \(n \times m \le 20\).
• Subtask \(2\) (\(10\) điểm): \(n = 2\).
• Subtask \(3\) (\(15\) điểm): \(n \le 10\).
• Subtask \(4\) (\(15\) điểm): \(n \le 15\).
• Subtask \(5\) (\(20\) điểm): Dữ liệu đảm bảo các cọc nằm trên cùng cột thì có màu giống nhau.
• Subtask \(6\) (\(30\) điểm): Không có ràng buộc nào thêm.