Description

以下描述不遵守任何物理规律。
在平面上，整齐排列着\(n\)行带电粒子，其中每行又有\(m\)个带电粒子，即所有带电粒子构成了一个大小为\(n×m\)的矩阵。每个粒子要么带正电，要么带负电，忽略粒子之间的相互作用力。由于某种特殊的原因，若一个边长为\(k\)的正方形包含的所有粒子都带正电，那么就会形成强度为\(k\)的电场。为了使问题更有趣，我们还会将某个正电粒子修改为负电粒子，你的任务是求出每次修改后所有正电粒子能形成的最大的电场强度。

Format

Input

第一行有\(3\)个整数\(n, m, q\)。
然后有\(n\)行，每行有一个长度为\(m\)的字符串，+表示正电粒子，-表示负电粒子。
然后有\(q\)行，每行\(2\)个整数\(x, y\)，表示将第\(x\)行第\(y\)列的正电粒子修改为负电粒子，保证修改前第\(x\)行第\(y\)列的粒子带正电。

Output

有\(q\)行，每行一个整数此次修改后所有正电粒子能形成的最大的电场强度。

Sample 1

Input

5 5 5
+-+++
+++++
+++++
+++++
++++-
1 5
2 2
5 3
2 3
1 1 

Output

4
3
3
2
2

Limitation

2s, 512MiB for each test case.

Hint

数据范围与约定

对于所有数据， \(1≤ n ,m ≤ 2×10^3, 1 ≤ q ≤ 10^4\)。

测试点编号	\(n, m\)	\(q\)
1~4	\(≤10\)	\(=1\)
5~8	\(≤50\)	\(≤10\)
7~12	\(≤10^3\)	\(=1\)
13~16	\(≤10^3\)	\(≤10^3\)
17~20	\(≤2×10^3\)	\(≤10^4\)

Source

CSP2019模拟试题五