E. Машины зогсоол

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

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

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

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

Петя ажил дээрээ уйдсан байгаа тул ажлынхаа машины зогсоолыг харж цаг нөхцөөж байлаа. Тэдний машины зогсоол нь дээрээсээ $n × m$ хэмжээтэй хүснэгт шиг харагддаг (нэг машины зогсоол нь хүснэгтийн нэг нүдтэй харгалзана). Машины зогсоолын зарим зогсоол нь машинтай үлдсэн нь хоосон байна.

Петя машинуудыг зогсоол руу нэг нэгээрээ орохыг харж байна. Дараа нь машинууд зогсоолд байраа эзэлж байгаа. Хэрвээ бид машины зогсоолыг дээрээс нь харж чадаж байгаа бол Петя хоосон зогсоолын хамгийн их тэг дөрвөлжний талбайг (өөрөөр хэлбэл квадрат) тооцоолохыг хүсэж байна. Мөн тэр өөрийн тэмдэглэлийн дэвтэр дээрээ талбайн хэмжээг (талуудын урт) тэмдэглэж авсан.

Чиний даалгавар бол: Зогсоолын эхний байдал өгөгдсөн ба машин орж ирэх бүрт Петя тэмдэглэлийн дэвтэр дээрх тэмдэглэлээ шинэчилнэ. Одоо үд дунд болж байна иймээс зогсоолоос машин гарахгүй.

Оролт

Эхний мөрөнд $n$, $m$, $k$ ($1 ≤ n, m, k ≤ 2000$) гурван бүхэл тоо агуулна. Эдгээр нь машины зогсоолын хэмжээнүүд ба Петя харж эхэлснээс хойш орж ирсэн машины тоо. Дараагийн $n$ мөр бүр нь $m$ тэмдэгтүүд агуулна. "X" нь машинтай зогсоолыг, '$.$' нь хоосон зогсоолыг илэрхийлнэ. Дараагийн '$k$' мөр бүр хос бүхэл $x_{i}$, $y_{i}$ тоонуудыг агуулна. Эдгээр нь харгалзан машинтай зогсоолын мөр болон баганын дугаар юм ($1 ≤ x_{i} ≤ n$, $1 ≤ y_{i} ≤ m$). Энэ газар нь хоосон байсан нь баталгаатай юм. Эхний машин зогсоолд амжилттай байраа эзэлсний дараа л дараагийн машин зогсоолоо хайна.

Гаралт

$k$ ширхэг бүхэл тоонууд хэвлэнэ. Энэ нь машинууд харгалзах зогсоолд байраа эзэлсний дараах хамгийн том хоосон талбайн талын урт юм.

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

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

Оролт
7 8 4
........
X.....X.
........
........
.X......
........
........
1 5
6 4
3 5
4 6
Гаралт
5
4
4
3
Сэтгэгдлүүдийг ачааллаж байна...