Description

一开始他会告诉你当前这块地的情况，但是小 D 有一些假操作，希望你操作给他看：

1. 由小 D 指定 $w$ 个位置，他希望知道其中哪个位置下水泡温泉的范围最大。泡温泉的范围定义为指定位置通过向上下左右四个方向能到达的位置的个数。若询问的位置为土，则范围为 $0$。如果如果有多个位置均为最大，输出给出顺序较前的那个。位置编号为 $1,2,...,w$。

2. 由小 D 指定 $w$ 个位置，他会使用魔法按顺序翻转这 $w$ 个地方的地形。即若原位置是土，则该位置变为温泉；若原位置是温泉，则该位置变为土。因为小 D 不希望活动范围减少得太快，所以他在将温泉变为土时不会将一个区域分割。

Input Format

第一行输入两个整数，$N,M$，为土地大小。

接下来的 $N$ 行每行输入 $M$ 个字符，为 .（代表温泉）或 *（代表土）

第 $N+2$ 行输入一个整数，$Q$，为操作数量。

接下来的 $Q$ 行，每行先读入两个整数 $opt$ 和 $w$，表示操作类型和指定点的数量，在同一行还有 $2w$ 个数 $x_{1},y_{1},x_{2},y_{2},...,x_{w},y_{w}$，分别表示 $w$ 个操作的位置为 $(x_{1},y_{1}),(x_{2},y_{2}),...,(x_{w},y_{w})$。

Output Format

对于每个操作 1，输出询问的答案并换行

5 5
.*...
.****
*....
*****
.....
3
1 2 1 1 1 3
2 1 3 1
1 2 1 1 1 3

2
1

Hint

对于 $30\%$ 的数据，$N,M\le 100,\sum w\le 100$

对于 $70\%$ 的数据，$N,M\le 1000$

对于 $100\%$ 的数据，$1\le NM,Q\le 10^{6},\sum w\le 10^{6},w\geq 1$

数据在 Windows 下制作