K. Туршилт

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

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

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

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

Та нэгэн шинэ зэвсгийн туршилтанд оролцохоор иржээ. Туршилтанд зориулан $1 × 1$ хэмжээтэй нүднүүдэд хуваагдсан $n × m$ хэмжээтэй дөрвөлжин талбай бэлтгэжээ. Тус талбай нь $k$ ширхэг обьект агуулах ба обьект тус бүр нь хэд хэдэн нүднээс бүрдсэн тэгш өнцөгт хэлбэртэй байх бөгөөд талууд нь талбайн талуудтай паралель байрлах юм. Обьектууд нь бие биетэйгээ давхцахгүй, бие биетэйгээ шүргэлцэхгүйгээр байрлана.

Зэвсгийн ажиллах зарчим нь маш нууц. Та энэхүү зэвсгээр хэд хэдэн нүднээс тогтсон дурын нэг тэгш өнцөгт хэлбэртэй талбай руу буудах боломжтой гэдгийг л мэдэж байгаа. Таны даалгавар: та нэгээс бага, гурваас их обьект онох ёсгүй. Обьект тус бүр нь тухайн талбай дотроо (энэ тохиолдолд оносонд тооцно) эсвэл тухайн талбайн гадна байх ёстой.

Зэвгээр буудаж болох аргуудын тоог олно уу.

Оролт

Эхний мөр нь $n$, $m$, $k$ ($1 ≤ n, m ≤ 1000$, $1 ≤ k ≤ 90$) гэсэн гурван бүхэл тоо агуулах ба эдгээр нь туршилтын талбайн хэмжээ, обьектуудын тоог тус тус харуулна. Дараагийн $n$ мөрүүд нь тур бүрдээ $m$ тооны тэмдэгтүүд байх бөгөөд эдгээр нь туршилтын талбайн тодорхойлолтыг агуулна.

"*" тэмдэгт нь тухайн квадрат нь обьект агуулсан байгааг илэрхийлэх бол "." нь хоосон орон зай байгааг харуулна. "*" тэмдэгтүүд нь бодлогын нөхцөлд нийцсэн яг $k$ тооны тэгш өнцөгт обьектыг бүрдүүлнэ.

Гаралт

Зэвсгээр буудаж болох хэдэн боломж байгааг харуулах нэг тоо гарга.

Орчуулсан: Энхгэрэл

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

Оролт
3 3 3
*.*
...
*..
Гаралт
21
Оролт
4 5 4
.*.**
...**
**...
...**
Гаралт
38
Оролт
2 2 1
.*
..
Гаралт
4
Сэтгэгдлүүдийг ачааллаж байна...