You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

小D最喜欢泡温泉了。小D找某奸商租下了一块$N$行$M$列的地，左上角为$(1,1)$，右下角为$(N,M)$。小D本以为这块地里全是温泉，结果这块地极不稳定，曾经发生过一些地形变动，所以其中一些地方全是土。

题目描述

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

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

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

输入格式

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

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

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

接下来的$Q$行，每行先读入两个整数$opt$和$w$，表示操作类型和指定点的数量，在同一行还有$2\times w$个数$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})$。

输出格式

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

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

2
1

提示

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

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

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

数据在windows下制作