#1487 · Tô màu

Cho một bảng hình chữ nhật gồm N dòng và M cột. Các dòng được đánh số từ 1 đến N, các cột được đánh số từ 1 đến M, giao của dòng i và cột j là ô (i, j). Có K màu được đánh số từ 1 đến K. Cần tô mỗi ô trong bảng bằng một trong K màu trên (không nhất thiết phải sử dụng toàn bộ K màu).

Tuy nhiên, sẽ có các ràng buộc về tương quan màu sắc giữa các ô kề nhau. Các ràng buộc này được mô tả bằng hai bảng kí tự H (gồm N dòng, M 1 cột) và V (gồm N− 1 dòng, M cột). Cụ thể:

• Nếu H_{i,j} = E thì hai ô (i, j) và (i,j+1) phải cùng màu với nhau
• Nếu H_{i,j} = N thì hai ô (i, j) và (i, j + 1) phải khác màu với nhau
• Nếu V_{i,j} = E thì hai ô (i, j) và (i + 1, j) phải cùng màu với nhau
• Nếu V_{i,j} = N thì hai ô (i, j) và (i + 1, j) phải khác màu với nhau

Hãy tìm một cách tô màu bất kì sao cho ít nhất 75% số lượng các ràng buộc trên được thỏa mãn, hoặc in ra -1 nếu không có cách tô.

• Dòng đầu tiên gồm số nguyên N, M, K (2 ≤ N, M ≤ 1 000, 1 ≤ K ≤ N × M) — số dòng và số cột của bảng chữ nhật.
• N dòng tiếp theo, mỗi dòng gồm một xâu độ dài M - 1, chỉ gồm kí tự E hoặc N — bảng kí tự H.
• N − 1 dòng tiếp theo, mỗi dòng gồm một xâu độ dài M, chỉ gồm kí tự E hoặc N — bảng kí tự V.

• Nếu có một cách tô màu thỏa mãn ít nhất 75% số lượng ràng buộc, in ra N dòng, mỗi dòng gồm M số nguyên có giá trị từ 1 đến K mô tả cách tô màu cho các ô trong bảng.
• Ngược lại, in ra -1.