ในปี 20XX ที่จะถึงนี้ เทศกาลสารสนเทศศาสตร์นานาชาติ (International Omatsuri in Informatics) จะจัดขึ้นที่ประเทศญี่ปุ่น เพื่อเตรียมความพร้อมสำหรับการจัดงาน คุณได้รับมอบหมายให้ออกแบบโลโก้สำหรับเทศกาลนี้

โลโก้ของเทศกาลสารสนเทศศาสตร์นานาชาติในแต่ละครั้งจะถูกสร้างขึ้นโดยใช้ภาพพื้นฐานภาพหนึ่ง ภาพนี้ประกอบด้วยช่องสี่เหลี่ยมจัตุรัสจำนวนหนึ่งที่เลือกมาจากตารางรูปสี่เหลี่ยมผืนผ้าที่มีความกว้างในแนวนอน $W$ ช่อง และความสูงในแนวตั้ง $H$ ช่อง ในครั้งนี้คุณตัดสินใจที่จะระบายสีภาพนี้ด้วยสีแดงและสีขาวซึ่งเป็นสีของธงชาติญี่ปุ่นเพื่อทำเป็นโลโก้ เพื่อไม่ให้งานระบายสีซับซ้อนเกินไป ใน $1$ ช่องสามารถใช้ได้เพียง $1$ สีเท่านั้น

เพื่อตัดสินใจว่าจะระบายสีอย่างไรดี คุณจึงขอคำแนะนำจากเพื่อนนักออกแบบ ตามรสนิยมทางศิลปะอันยอดเยี่ยมของเขา การออกแบบที่พึงประสงค์คือทั้งบริเวณที่ระบายสีแดงและบริเวณที่ระบายสีขาวจะต้องเป็นรูปที่มีความสมมาตรตามแกน นอกจากนี้ เมื่อพิจารณาถึงความสมดุลของสี เขายังบอกอีกว่าจำนวนช่องที่ระบายสีแดงควรมีจำนวน $K$ ช่อง เนื่องจากเขาไม่ได้บอกวิธีระบายสีที่เป็นไปตามเงื่อนไขเหล่านี้ให้คุณ คุณจึงต้องหาวิธีระบายสีด้วยตนเอง เมื่อกำหนดภาพและค่าของ $K$ มาให้ จงเขียนโปรแกรมเพื่อหาวิธีระบายสีที่สอดคล้องกับเงื่อนไขมา $1$ วิธี

ข้อมูลนำเข้า

บรรทัดที่ $1$ มีจำนวนเต็ม $3$ จำนวน คือ $W, H, K$ ($1 \le W \le 40$, $1 \le H \le 40$, $1 \le K \le WH - 1$) คั่นด้วยช่องว่าง ซึ่งแทนความกว้าง ความสูงของภาพที่กำหนดให้ และจำนวนช่องที่ต้องระบายสีแดง

อีก $H$ บรรทัดถัดไปแทนข้อมูลของภาพ ในบรรทัดที่ $i + 1$ ($1 \le i \le H$) มีเลข $W$ ตัวซึ่งแต่ละตัวเป็น $0$ หรือ $1$ คั่นด้วยช่องว่าง เมื่อจำนวนเต็มตัวที่ $j$ ($1 \le j \le W$) ในบรรทัดที่ $i + 1$ เป็น $1$ หมายความว่าช่องที่แถวที่ $i$ จากด้านบนและคอลัมน์ที่ $j$ จากด้านซ้ายถูกใช้ในภาพ และเมื่อเป็น $0$ หมายความว่าช่องนั้นไม่ได้ถูกใช้ในภาพ ในภาพจะมีการใช้ช่องอย่างน้อย $2$ ช่องเสมอ รับประกันว่าค่าของ $K$ จะน้อยกว่าจำนวนช่องที่ถูกใช้ในภาพ

สำหรับทุกข้อมูลนำเข้าที่ใช้ในการตรวจให้คะแนน จะมีวิธีระบายสีที่สอดคล้องกับเงื่อนไขอย่างน้อย $1$ วิธีเสมอ

ข้อมูลส่งออก

ให้แสดงผลออกทางเอาต์พุตมาตรฐาน จงแสดงจำนวนเต็มที่แทนวิธีระบายสี โดยแสดงบรรทัดละ $W$ จำนวนคั่นด้วยช่องว่าง เป็นจำนวน $H$ บรรทัด เมื่อจำนวนเต็มตัวที่ $j$ ในบรรทัดที่ $i$ เป็น $1$ แทนการระบายสีแดงลงในช่องที่แถวที่ $i$ จากด้านบนและคอลัมน์ที่ $j$ จากด้านซ้าย และเมื่อเป็น $2$ แทนการระบายสีขาวลงในช่องนั้น สำหรับช่องที่ไม่ได้ถูกใช้ในภาพ ให้แสดง $0$

หากมีวิธีระบายสีที่เป็นไปได้หลายวิธี สามารถแสดงวิธีใดก็ได้

เกณฑ์การให้คะแนน

ในข้อมูลที่ใช้สำหรับการตรวจให้คะแนน คะแนนส่วน $20\%$ ของคะแนนทั้งหมดจะเป็นไปตามเงื่อนไข $W, H \le 5$

ตัวอย่างข้อมูลนำเข้า 1

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

ตัวอย่างข้อมูลส่งออก 1

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

ข้อมูลส่งออกนี้สอดคล้องกับการระบายสีดังต่อไปนี้ ช่องสีเทาแทนการระบายสีแดง และช่องสีขาวแทนการระบายสีขาว เส้นประและเส้นจุดคือแกนสมมาตรของบริเวณสีแดงและบริเวณสีขาวตามลำดับ

การระบายสีดังต่อไปนี้ไม่สอดคล้องกับเงื่อนไข: