Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.

Мали Перица воли да игра шах, али често губи ствари и заборавља правила. Родитељи су му због тога купили много гарнитура и табли за шах, међутим он их је све изгубио, осим топова који су му омиљене фигуре па их због тога држи у посебној фиоци.

Перица је одлучио да се игра и покушао да се сети правила шаха, за почетак сећа се да је постојала табла па је због тога на картону нацртао таблу са \(N\) врста и \(M\) колона. Одлучио је да свако поље или остави празно или да у њега стави тачно једну од шест врста играчака којих највише има, наиме или аутић или коцкицу на којој је написан неки од бројева 0 до 4.

Нажалост, једини део шаха ког се Перица сећа, сем поменутих, је начин на који се помера топ, то му је ипак омиљена фигура (за оне који ни то не знају, топ се у једном потезу може померити на неко друго поље у својој колони или врсти). Зато је одлучио да постави известан број топова на празна поља своје табле и помера их, наравно без подизања са табле, па топ не може да пређе преко поља на ком се већ налази нека играчка. Док је то чинио схватио је да игра није превише занимљива ако је на табли превише топова, јер се често налазе један другоме на путу, а ни ако је на табли премало топова јер у том случају нема чиме да се игра, па је увео следећа правила:

  1. Ни један топ се не сме налазити на пољу на које други топ може да дође у једном потезу.
  2. Уколико је на неком пољу коцкица са бројем \(К\), на њему суседним пољима мора да се налази тачно \(К\) топова. (Поља су суседна ако деле страницу, дакле свако поље има највише четири суседна поља.)
  3. За свако поље које је на почетку игре било празно мора на табли постојати топ који у највише једном потезу може да дође на то поље.

Перица је брзо приметио да пре него што почне да се игра мора прво да пронађе почетну поставку топова, уколико таква уопште постоји, а која поштује наведена правила за његову таблу. Ваш задатак је да помогнете Перици да почне да се игра тако што ћете за задату почетну таблу пронаћи поставку топова која поштује сва задата правила, или закључити да таква табла не постоји.

Опис улаза

У првој линији улаза налазе се два цела броја, \(N\) - број врста и \(M\) - број колона табле. У свакој од наредних \(N\) линија улаза налази се по \(M\) знакова (‘.’, ‘#’, ‘0’, ‘1’, ‘2’, ‘3’ или ‘4’), који означавају да се у одговарајућем пољу ‘.’ - не налази ништа (празно је) ‘#’ - налази аутић ‘0’, ‘1’, ‘2’, ‘3’ или ‘4’ - налази коцкица која показује одговарајући број.

Опис излаза

Уколико тражена конфигурација не постоји исписати \(-1\), док уколико постоји потребно је исписати матрицу димензија улазне матрице, чија су поља иста као одговарајућа поља у улазној матрици, с тим да се празно поље, ‘.’, може заменити са ‘C’ уколико на то поље треба ставити топа у поставци.

Пример 1

Улаз

5 6
.#01.1
2.....
0.....
......
#...2.

Излаз

C#01C1
2C....
0.....
..C...
#..C2C

Пример 2

Улаз

2 2
0.
.2

Излаз

-1

Ограничења

У свим примерима важи \(1 \leq N, M \leq 10\).