E. Онцгой график

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Та $n × m$ хэмжээтэй торон графикийн асуудлыг шийдвэрлэх хэрэгтэй байна. Графикын орой нь $n × m$ хэмжээтэй торны зангилаанууд юм. Графикын ирмэг нь сүлжээний нэгж квадрат бүрийн талууд мөн диогналиуд юм.

Доорх зурагт 3 × 5 графикыг харуулсан байна. Хар шугамууд нь графикийн ирмэгүүд, өнгийн дугуйнууд нь графикийн орой байна. Графикын оройнуудыг шалтгаантайгаар будсан: Графикын оройг зөв будсан ба 3 × 5 графикыг дөрвөн өнгөөр будсан. Хэрвээ график зөв будагдсан бол орой бүр нь будагдсан ба ямар ч ирмэгээр холбогдсон хоёр орой ижил өнгөөр будагдаагүй байна.

Чамд $n × m$ торон графикийн хэмжээ мөн зарим оройн өнгийг өгсөн байна. Графикын оройг 4 өнгөөр зөв будахын тулд графикын будагдаагүй оройнуудыг хэрхэн будах арга замыг олно. Хэрвээ графикын орой зөв будагдаагүй бол хариулт байхгүй байна гэж хэлж болно.

Оролт

Эхний мөр нь $n$ ба $m$ $(2 ≤ n, m ≤ 1000)$ хоёр бүхэл тоог агуулна. Дараагийн $n$ мөр бүр нь өгөгдсөн графикын $m$ тэмдэгтүүдийг агуулна. Тэмдэгт бүр нь «$0$», «$1$», «$2$», «$3$», «$4$»-ийн аль нэг байна. «$0$» тэмдэг нь тухайн орой будагдаагүй байна гэсэн үг ба бусад тэмдэг нь тухайн орой будагдсан байна гэсэн үг юм.

Боломжтой бүх өнгө нь $1$-с $4$ хүртэл дугаарлагдсан байна гэж үзнэ.

Гаралт

Хэрвээ графикын зөв оройнуудыг будах боломжгүй бол нэг мөрөнд 0 гэж хэвлэнэ. Эсрэг тохиолдолд $n × m$ будагдсан графикыг хэвлэнэ. Графикыг оролттой ижил загвараар хэвлэнэ.

Хэрвээ олон хариулт байгаа бол тэдгээрээс аль нэгийг хэвлэнэ.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
3 5
10101
00020
01000
Гаралт
13131
42424
31313
Оролт
2 2
00
00
Гаралт
12
34
Оролт
2 2
11
00
Гаралт
0

Тэмдэглэл

Эхний жишээний хариулт зураг дээр харагдаж байна. (1 -- ногоон өнгө, 2 -- цэнхэр, 3 -- хөх, 4 -- ягаан).

Хоёр дахь жишээнд 4 хариулт байна. Хариулт бүрийг зөв гэж үзэж болно.

Гуравдахь жишээний хувьд холбогдсон хоёр орой ижил өнгөөр будагдсан байна. Тиймээс зөв оройн будалт олж чадахгүй.

Сэтгэгдлүүдийг ачааллаж байна...