Vào năm \(20XX\), Lễ hội Tin học Quốc tế (International Omatsuri in Informatics) sẽ được tổ chức tại Nhật Bản. Bạn được giao thiết kế biểu trưng cho lễ hội.

Biểu trưng được tạo từ một hình có sẵn, gồm một số ô vuông trong một bảng hình chữ nhật rộng \(W\) ô và cao \(H\) ô. Bạn muốn tô hình này bằng hai màu đỏ và trắng của quốc kỳ Nhật Bản. Mỗi ô thuộc hình phải được tô bằng đúng một màu.

Một nhà thiết kế khuyên bạn chọn cách tô sao cho vùng màu đỏ và vùng màu trắng đều là những hình đối xứng qua một đường thẳng. Hai vùng không bắt buộc có cùng trục đối xứng. Ngoài ra, để cân đối màu sắc, phải có đúng \(K\) ô được tô đỏ.

Yêu cầu

Cho hình ban đầu và số \(K\), hãy tìm một cách tô thỏa mãn các điều kiện trên. Mỗi vùng màu được xét như hợp của toàn bộ các ô vuông được tô màu đó.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa ba số nguyên \(W,H,K\), lần lượt là chiều rộng, chiều cao của bảng và số ô cần tô đỏ.
• Trong \(H\) dòng tiếp theo, mỗi dòng chứa \(W\) số nguyên bằng \(0\) hoặc \(1\). Số thứ \(j\) trên dòng thứ \(i\) của phần này cho biết ô ở hàng \(i\) tính từ trên xuống, cột \(j\) tính từ trái sang: \(1\) nghĩa là ô thuộc hình, \(0\) nghĩa là ô không thuộc hình.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Dữ liệu ra

Ghi ra đầu ra chuẩn \(H\) dòng, mỗi dòng gồm \(W\) số nguyên cách nhau bởi dấu cách. Số ở hàng \(i\), cột \(j\) phải là:

• \(1\) nếu ô tương ứng được tô đỏ;
• \(2\) nếu ô tương ứng được tô trắng;
• \(0\) nếu ô tương ứng không thuộc hình ban đầu.

Nếu có nhiều cách tô hợp lệ, có thể xuất bất kỳ cách nào. Bài sử dụng bộ kiểm tra đáp án để xác nhận cách tô; không yêu cầu kết quả trùng từng số với ví dụ.

Ràng buộc

• \(1\le W,H\le40\).
• \(1\le K\le WH-1\).
• Hình ban đầu có ít nhất hai ô; \(K\) nhỏ hơn số ô thuộc hình.
• Luôn tồn tại ít nhất một cách tô hợp lệ.
• Giới hạn thời gian: \(3\) giây cho mỗi test.
• Giới hạn bộ nhớ: \(64\) MB.

Phân nhóm

Bài có \(25\) nhóm chấm, mỗi nhóm gồm đúng một test: lần lượt là 01, 02, ..., 25. Mỗi nhóm được \(4\) điểm nếu xuất một cách tô hợp lệ, tổng cộng \(100\) điểm.

Các test tương ứng với \(20\%\) tổng số điểm thỏa mãn \(W,H\le5\).

Ví dụ

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

0 2 0 0
1 0 2 1
2 0 0 0

Kết quả trên tương ứng với hình dưới đây. Ô màu xám biểu diễn ô được tô đỏ; ô màu trắng biểu diễn ô được tô trắng. Đường nét đứt và đường chấm lần lượt là trục đối xứng của vùng đỏ và vùng trắng.

Cách tô sau không hợp lệ vì vùng đỏ không đối xứng qua một đường thẳng:

Cách tô sau không hợp lệ vì số ô đỏ không bằng \(2\):