Алдағы 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$ сандары жазылған. $i + 1$-ші жолдағы $j$-ші ($1 \le j \le W$) бүтін сан $1$ болғанда, бұл жоғарыдан санағанда $i$-ші, солдан санағанда $j$-ші торкөздің суретте қолданылатынын, ал $0$ болғанда ол торкөздің суретте қолданылмайтынын білдіреді. Суретте міндетті түрде кемінде $2$ торкөз қолданылады. $K$ мәні суретте қолданылған торкөздер санынан қатаң кіші екеніне кепілдік беріледі.

Бағалауға қолданылатын кез келген кіріс деректерде шарттарды қанағаттандыратын кемінде $1$ бояу әдісі бар.

Шығыс деректер

Шығаруды стандартты шығысқа орындау керек. Бояу әдісін білдіретін бүтін сандарды $H$ жол бойы, әр жолда бос орын арқылы бөлінген $W$ саннан шығарыңыз. $i$-ші жолдағы $j$-ші бүтін сан $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

Бұл шығыс келесі бояу әдісіне сәйкес келеді. Сұр торкөздер қызылға бояуды, ал ақ торкөздер аққа бояуды білдіреді. Үзік сызық пен нүктелі сызық сәйкесінше қызыл аймақ пен ақ аймақтың симметрия осьтері болып табылады.

Келесі бояу әдістері шарттарды қанағаттандырмайды: