← 返回题目列表

Codeforces · 480/E

E. 停车场

中文机器翻译题面 查看原题

Petya 工作很无聊,他通过观察办公室的停车场来消磨时间。从上方看,停车场就像一张 n × m 的桌子(桌子的一个单元对应一个停车位)。停车场有些车位已被占用,有些则空着。

Petya 看着汽车一辆接一辆驶入停车场。当一辆车停在停车位后,佩蒂亚(Petya)自娱自乐地计算着如果我们从上方看的话,停车场上可以看到的空位(即方形子表)的最大平方是多少。此外,他还在笔记本上记下正方形的大小(边长)。

你的任务是:给定初始时刻停车场的状态以及到达车辆停放位置的信息,恢复Petya在笔记本上写的内容。现在是中午,没有人离开停车场。

输入

第一行包含三个整数 n、m 和 k——Petya 开始值班后停车场的大小和到达车辆的数量 (1 ≤ n, m, k ≤ 2000)。以下 n 行中的每一行包含 m 个字符“X”和“.”,其中“X”表示拍摄点,“.”表示拍摄点。意思是空的地方。接下来的 k 行中的每一行都包含一对整数 xi, yi — 相应汽车所在地点的行数和列数 (1 ≤ xi ≤ n, 1 ≤ yi ≤ m)。可以保证这个地方是空的。您可以假设只有在前一辆车成功找到停车位后,一辆车才会进入停车场。

输出

打印k个整数——相应车辆进入停车场后空车位最大正方形的边长。

示例

输入 #1

7 8 4
........
X.....X.
........
........
.X......
........
........
1 5
6 4
3 5
4 6

输出 #1

5
4
4
3