436C орчуулах · Codeforces.mn

# Шорон ба чихэр
"Шорон ба чихэр" тоглоом ачааллаж байх үед та серверээс $k$ үеийн тайлбарыг авах шаардлагатай. Тайлбар бүр $n × m$ хэмжээтэй тэгш өнцөгт талбарын зураг байна. Талбарын зарим нүд нь чихэр агуулж болно (нүд бүр хамгийн ихдээ нэг чихэртэй байна). Зураг дээр хоосон нүдийг "$.$" тэмдэгтээр харин уг нүдэнд чихэр байвал Англи цагаан толгойн үсгээр тэмдэглэгдэнэ. Нэг үед төстэй чихрүүд байж болох ба энэ тохиолдолд зураг дээрх харгалзах нүднүүдийн үсэг нь адилхан байна.

![](http://codeforces.com/predownloaded/bd/9f/bd9f8ac5dbefb059b291818969b7aa27f210112b.png)

Та сүлжээгээр мэдээлэл дамжуулахдаа ачааллыг бага байлгахыг хүсэх буюу дамжуулсан мэдээллийн нийт хэмжээг хамгийн бага байлгахыг хүснэ. Үеүүдийг дурын дарааллаар дамжуулж болно. Тухайн $A$ үеийг дамжуулах хоёр зам байна:
  
  1. Та $A$ үеийг бүхлээр нь дамжуулж болно. Ингэхдээ та сүлжээгээр $n\*m$ байт дамжуулах хэрэгтэй.
  2. Та $A$ үе болон өмнө нь дамжуулагдсан $B$ (хэрвээ оршин байвал) үеүүдийн ялгааг дамжуулж болно; энэ үйлдэл нь $d\_{A, B}*w$ байтыг дамжуулахыг шаардах ба энд $d\_{A, B}$ нь $A$ болон $B$-н хувьд талбарын ялгаатай нүднүүдийн тоо ба $w$ нь тогтмол тоо байна. Та $d\_{A, B}$ утгыг тооцоолохын тулд $A$ болон $B$ үеүүдийн нүднүүдийг л харьцуулах ёстой. Та үеүүдийн зургийг өөрчилж болохгүй буюу өөрөөр нэг нэгэнтэй нь харьцангуйгаар эргүүлж мөн шилжүүлж болохгүй.

Таны ажил бол бүх $k$ үеийг хамгийн бага ачаалалтайгаар дамжуулах аргыг олох юм.

## Оролт
Эхний мөрөнд дөрвөн бүхэл тоон утга $n, m, k, w$ $(1 ≤ n, m ≤ 10; 1 ≤ k, w ≤ 1000)$ байна. Тэгээд $k$ үеийн тайлбар байна. Үе бүр $n$ мөрөөр тодорхойлогдох ба мөр бүр $m$ тэмдэгт агуулна. Тэмдэгт бүр Англи цагаан толгойн үсэг эсвэл цэг ("$.$") байна. Үсгийн том жижиг байгаа эсэх нь хамаатай байна.

## Гаралт
Эхний мөрөнд дамжуулагдсан байтын шаардлагатай хамгийн бага тоог хэвлэ.

Тэгээд $k$ ширхэг хос бүхэл тоо $x\_{1}, y\_{1}, x\_{2}, y\_{2}, ..., x\_{k}, y\_{k}$ хэвлэх ба эдгээр нь үеүүдийг дамжуулах замыг тодорхойлно. $x\_{i}$, $y\_{i}$ хос нь $x\_{i}$ үе нь $y\_{i}$ замаар дамжуулагдах шаардлагатайг илэрхийлнэ. Хэрвээ $y\_{i}$ нь 0-тэй тэнцүү бол уг үе нь эхний замыг ашиглан дамжуулагдсан гэсэн үг бол бусад тохиолдолд $y\_{i}$ нь өмнөх дамжуулагдсан үеийн дугаартай тэнцүү байна. Энэ нь та $x\_{i}$ үеийг дамжуулахын тулд $y\_{i}$ ба $x\_{i}$ үеүүдийн ялгааг дамжуулна гэсэн үг. Хос тоонуудыг үеүүдийг дамжуулах дарааллаар хэвлэнэ. Үеүүд оролтонд өгөгдсөн дарааллаараа 1-c $k$ хүртэл дугаарлагдана.

Хэрвээ тохиромжтой хэд хэдэн шийдэл байвал та алийг нь ч хэвлэж болно.

-- Г.Мэндбаяр

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

Оролт

2 3 3 2
A.A
...
A.a
..C
X.Y
...

Гаралт

Оролт

1 1 4 1
A
.
B
.

Гаралт

Оролт

1 3 5 2
ABA
BBB
BBA
BAB
ABB

Гаралт