问题描述

有一个 $N\times N$ 的方格棋盘。对第 $r$ 行第 $c$ 列的格子，记其为 $(r,c)$。每个格子要么被着色为 黑色，要么为 白色。当 $S_{r,c}$ 为 # 时表示黑色，为 . 时表示白色。

你得到 $Q$ 个查询。对于第 $i$ 个查询（$1\le i\le Q$），给出四个整数 $U_i,D_i,L_i,R_i$。

先对棋盘执行如下着色步骤：将所有不满足 $U_i\le r\le D_i$ 且 $L_i\le c\le R_i$ 的格子染成黑色。在此基础上，问你最多可以执行下面的操作多少次：

• 选择一对整数 $(r,c)$，要求四个格子 $(r,c),(r,c+1),(r+1,c),(r+1,c+1)$ 都为 白色，然后将这四个格子中的任意一个格子染成黑色（即把一个白格改为黑格）。

对于每个查询，独立地求解答案（即对于每个查询，均以初始棋盘开始，然后先把不在子矩形内的格子染黑，再计算最大操作次数）。

输入格式

• 第一行包含两个整数 $N$ 和 $Q$。
• 接下来 $N$ 行，每行 $N$ 个字符，字符为 . 或 #，表示初始棋盘中对应格子的颜色（. 表示白色，# 表示黑色）。第 $i$ 行第 $j$ 则为 $S_{i,j}$。
• 接下来 $Q$ 行，每行四个整数 $U_i,D_i,L_i,R_i$，表示第 $i$ 个查询的子矩形范围（包含边界）。

输出格式

输出 $Q$ 行，第 $i$ 行（$1\le i\le Q$）为第 $i$ 个查询的答案 —— 在按查询要求先染黑所有不在指定子矩形内的格子后，能执行上述操作的最大次数。

样例输入 1

5 4
..#.#
.....
#....
...#.
.#...
1 3 1 3
3 5 3 5
2 3 1 4
1 5 1 5

样例输出 1

2
0
2
5

样例输入 2

7 6
#.#....
.....#.
.......
.#..#.#
#....#.
.......
....##.
1 3 2 7
4 6 1 6
6 7 2 7
3 5 4 6
1 6 2 4
1 7 1 7

样例输出 2

4
4
2
0
6
13

说明

样例 $1$ 解释

考虑第一个问题。

将所有不满足 $1\le r\le 3$ 且 $1\le c\le 3$ 的格子涂黑后，网格如下。

..###
...##
#..##
#####
#####

你可以在此网格上按如下方式执行该操作两次。

• 选择 $(r,c)=(1,1)$。在格子 $(1,1),(1,2),(2,1),(2,2)$ 中，选择格子 $(1,2)$ 并将其涂黑。
• 选择 $(r,c)=(2,2)$。在格子 $(2,2),(2,3),(3,2),(3,3)$ 中，选择格子 $(2,2)$ 并将其涂黑。

你不能执行超过两次操作，所以在第一行输出 $2$。

数据范围

• $2 \le N \le 500$。
• $1 \le Q \le 2\times 10^5$。
• $S_{r,c} \in \{$., # $\}$。
• $1 \le U_i \le D_i \le N$，$1 \le L_i \le R_i \le N$。
• $N,Q,U_i,D_i,L_i,R_i$ 都为整数。