Васяд $n*m$ квадратад хуваагдсан $n × m$ тэгш өнцөгт бүхий маш үзэсгэлэнтэй цэцэрлэг байгаа. Нэг сайхан өдөр Вася ургамал агуулсан $k$ чухал квадратуудын хооронд зам байгуулах хэрэгтэй гэдгийг санасан. Зам малтахын тулд тэр өөрийн цэцэрлэгийн зарим квадратуудыг бетоноор хучиж чадна.

Цэцэрлэгийн квадрат бүрийн хувьд бид $a_{ij}$ тоог мэдэх ба энэ тоо нь $(i, j)$ координаттай квадратад ургасан цэцгийн тоо байна. Квадратыг бетоноор хучихад квадрат дотор ургасан бүх цэцэг үхнэ.

Вася дараах нөхцөлүүд биелэж байхаар зарим квадратуудыг бетоноор хучихаар шийдсэн:

• бүх $k$ квадратууд бетоноор хучигдсан байх ёстой
• чухал квадрат бүрээс өөр дурын чухал квадратруу очих зам байх ёстой. Бетоноор хучигдах зам нь нэг талтай квадратууд буюу хөрш квадратуудаас бүрдсэн зам байна.
• үхсэн ургамалуудын тоо хамгийн бага байх ёстой

Вася нилээн том цэцэрлэгтэй учир таны тусламжийг хүсч байна.

Оролт

Эхний мөрөнд гурван бүхэл тоон утга $n$, $m$ ба $k$ ($1 ≤ n, m ≤ 100$, $n*m ≤ 200$, $1 ≤ k ≤ min(n*m, 7$)) байх буюу цэцэрлэгийн хэмжээсүүд болон чухал квадратуудын тоо байна. Дараагийн $n$ мөр бүрт $m$ бүхэл тоон утга $a_{ij}$ ($1 ≤ a_{ij} ≤ 1000$) байх буюу квадратуудад байгаа цэцгүүдийн тоо юм. Дараагийн $k$ мөрөнд чухал квадратуудын координатууд "$x$ $y$" (хашилтгүйгээр) ($1 ≤ x ≤ n$, $1 ≤ y ≤ m$) хэлбэртэй байна. Бүх $k$ чухал квадратууд ялгаатай координаттай байна.

Гаралт

Эхний мөрөнд зам барих хугацаанд үхэх ургамалуудын хамгийн бага тоо болох бүхэл тоон утгыг хэвлэ. Тэгээд тус бүртээ $m$ тэмдэгт агуулсан $n$ мөр байх буюу цэцэрлэгийн төлөвлөгөө байна. Энэ төлөвлөгөөнд "$X$" (Латин том X үсэг) нь бетоноор хучигдсан квадратыг илэрхийлэх ба "." (цэг) нь бетоноор хучигдаагүй квадратыг илэрхийлнэ. Хэрвээ хэд хэдэн шийдэл байвал алийг нь ч хэвлэж болно.