题目描述

老师正在排座位，而且座位是随机排的。但是班里有两个人，只要他们 "相邻" 就说话。

这个班有 $n \times m$ 个座位，其中 . 表示空座位，# 表示不能坐的地方。

座位状态会发生改变，老师想知道每次改变后，随机安排两个学生到不同空座位时，他们相邻的概率是多少？

注意，$\{(a,b),(c,d)\}$ 和 $\{(c,d),(a,b)\}$ 算作两种情况。

输入格式

第一行两个正整数 $n,m$，表示教室的行列数。

接下来 $n$ 行，每行 $m$ 个字符，表示初始座位状态。

接下来一行一个正整数 $q$，表示操作次数。

接下来 $q$ 行，每行输入：

• 1 x y：切换座位 $(x,y)$ 的状态（从.变为#或从#变为.）
• 2：查询当前两人说话概率

输出格式

对于每个2操作，输出一个百分比，表示两人说话的几率，四舍五入保留十位小数。

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

39.0476190476%
36.2637362637%
39.0476190476%

数据范围与约定

$5 \le n,m \le 10^3$

$1 \le q \le 10^5$

$m\mod\ 3=2$

行列数从 $1$ 开始。

• 什么是 "相邻"？

  如果两人的座位八方向相接或两人是 "同桌"，则称两人 "相邻"。

• 什么是 "同桌"？

  如果一个人在第 $x$ 列且另一人在第 $x+2$ 列并在同一排，且不被过道隔开，则称两人为 "同桌"。

在列数 $k\ \%\ 3=1$ 和 $k\ \%\ 3=2$ 中间有一条过道

注意，教室里的第一列和最后一列是单独的