D. Дразил ба дөрвөлжин

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

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

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

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

Дразил $1 × 2$ хэмжээтэй дөрвөлжингүүдийг $n × m$ хүснэгтэнд өрөх тухай дараах бодлогыг боджээ:

"Хүснэгтийн зарим нүд хоосон, харин зарим нь будагдсан. $1 × 2$ хэмжээтэй дөрвөлжингүүдээр тэдгээрийг хооронд нь давхцуулалгүйгээр хүснэгтийн бүх хоосон зайг хуч. Мөн хэрхэн хучсанаа хэвлэ."

Гэвч Дразил энэхүү бодлогыг бодох тусгай програм бичихийг хүсэхгүй байв. Түүний найз Варда түүнд: "Тэмцээний оролцогчдоор нөхцөлийг хангах хучилт цор ганц байгаа үед хучилтыг хэвлүүлэн бусад тохиолдолд 'Not unique' гэж хэвлүүлбэл ямар вэ?" гэсэн санал тавив.

Дразил энэхүү хязгаарлалт нь анхны бодлогоос бүр ч хэцүү байж болохыг анзаарчээ. Энэхүү шинэ бодлогыг бодно уу.

Хэрэв хучих хувилбар байхгүй эсвэл хучих хувилбар нэгээс олон бол "Not unique" гэж хэвлэхийг анхаараарай.

Оролт

Оролтонд $n$ болон $m$ ($1 ≤ n, m ≤ 2000$) бүхэл тоонууд байна.

Дараачийн $n$ мөрөнд хүснэгтийн мөрүүдийн тайлбар байна. "." тэмдэгтээр хоосон нүдийг, харин "*" тэмдэгтээр будагдсан нүдийг тэмдэглэсэн байна.

Гаралт

Хэрэв хучих хувилбар байхгүй эсвэл хучих хувилбар нэгээс олон бол "Not unique" гэж хэвлэ.

Бусад тохиолдолд хүснэгтийг $1 × 2$ дөрвөлжнүүдээр хэрхэн хучиж болохыг хэвлэнэ. "<>" тэмдгээр хэвтээ дөрвөлжинг, харин "^v" тэмдгээр босоо дөрвөлжинг илэрхийлэн хэвлэ. Гаралтын форматыг жишээн дээр үзүүлсэн байна.

Орчуулсан: Бат-Од

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

Оролт
3 3
...
.*.
...
Гаралт
Not unique
Оролт
4 4
..**
*...
*.**
....
Гаралт
<>**
*^<>
*v**
<><>
Оролт
2 4
*..*
....
Гаралт
*<>*
<><>
Оролт
1 1
.
Гаралт
Not unique
Оролт
1 1
*
Гаралт
*

Тэмдэглэл

Эхний жишээнд хоёр боломжит хучилт бий:

<>^
^*v
v<>

болон

^<>
v*^
<>v

Тиймээс хариу нь "Not unique".

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