Республиканская олимпиада по информатике 2017 год, Павлодар

(Саперлер)

Ограничение по времени:

2 seconds

Ограничение по памяти:

256 megabytes

Екі сапер миналы алаңдағы миналарды тауып, оларды қауіпсіздендіру керек. Алаң өлшемдері $n \times m$ ($n$ жол және $m$ баған) кесте түрінде берілген және осы кестенің әрбір шаршысында көбінде 1 мина бола алады. Кестенің жолдары жоғарыдан төмен $1$-ден $n$-ге дейін және бағандары солдан оңға қарай $1$-ден $m$-ге дейін нөмірленген. Саперлер жұмысты мүмкіндігінше әділ жолмен бөлгісі келеді. Жұмыс әділ болу үшін алаң екі саперге бірдей бөліктерге (қандай да бір бұрғанда беттесу керек) бөліну керек және әділдік екі бөліктегі миналардың сандарындағы айырмашылығымен өлшенеді. Алаңды тек қана шаршылардың қабырғаларымен ғана бөлуге болады және де бөліктер өзара байланысты болу керек, яғни бір бөліктің әрбір шаршысынан кез келген басқа шаршысына қабырғасы бойынша көршілес шаршылар арқылы жету мүмкін болу керек. Сіздің тапсырмаңыз алаңды екі саперге мүмкіндігінше әділ жолмен бөліп беретін программа жазу. $m$ санының жұп екендігіне кепілдік берілген.

Формат входного файла

Бірінші жолда екі бүтін $n$($1\le n \le 1000$) және $m(1 \le m \le 1000)$ сандары жазылған. Келесі $n$ жолдың әрқайсысы $m$ символдан тұрады, бұл символдар алаңды сипаттайды. Егер символ «.» болса, бұл шаршыда мина жоқ және егер символ «*» болса, бұл шаршыда мина бар дегенді білдіреді.

Формат выходного файла

Жауап ретінде «1» және «2» символдарынан тұратын әрқайсысы $m$ символдан құралған $n$ жол шығару керек. «1» символы осы шаршы бірінші сапердікі және «2» символы осы шаршы екінші сапердікі екенін білдіреді.

Система оценки

Бұл есепте 100 тест. Әр өткен тест үшін қатысушы $1$ ұпай алады.

Пример:

Вход

5 8
**.....*
...*.*..
*..*....
*....*..
.......*

Ответ

11111111
22222211
22112211
22111111
22222222

( Batyrkhan Orynkul )