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.

Hình vẽ minh họa cho ví dụ. Màu cam tương ứng với màu 1, màu xanh lá cây tương ứng với màu 2, màu xanh biển tương ứng với màu 3. Các kí hiệu màu đen là ràng buộc được thỏa mãn, màu đỏ là ràng buộc không được thỏa mãn.

Có 13 trên 17 ràng buộc được thỏa mãn, tỉ lệ không dưới 75%. Do đó, cách tô màu này thỏa mãn điều kiện đề bài.