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