配点 : 100 点
注意
此问题的内存限制为 384 MiB。 您将获得一个由
問題文
2N+1 行 2N+1 列组成的网格。在这里, N 是正整数。从网格上方 i 第几行,从左边开始 j 柱方 (1 \le i, j \le 2N + 1) 只需将其移至 (i, j) 。鳟鱼 (i, j) 是一个字符 S_{i,j} 被写入并满足以下属性。
- i 是奇数,
当 j 为奇数时,
当 S_{i, j} =
o - i 是奇数,
当 j 为偶数时, S_{i, j} =
-或 至少. - i 是偶数, j 为奇数时,
当 S_{i, j} =
|或 至少. - i 是偶数, j 为偶数时, S_{i, j} =
.
独立查询 给出了 Q 。 i 個目 (1 \le i \le N) 时,奇数 鉴于 U_i, D_i, L_i, R_i (1 \le U_i \le D_i \le 2N+1,\ 1 \le L_i \le R_i \le 2N+1) ,请回答以下问题。
部分网格 在 [U_i, D_i] \times [L_i, R_i] 中,字符
o作为顶点、字符 求-和 按字典顺序比较|为边时无向图的连通分量数。
具体回答以下问题。
((D_i - U_i + 2) / 2) \times ((R_i - L_i + 2) / 2) 顶点无向图 创建 G 和顶点是 小于或等于 U_i 以上 D_i 的奇数 x 和 按字典顺序比较 L_i 以上 R_i 的奇数 y 对 假设用 (x, y) 表示。另外,无向图 G 具有以下无向边并且没有其他无向边。 如果满足
- 奇数 x, y 是 在 U_i \le x \le D_i,\ L_i \le y \le R_i - 2 和 S_{x,y+1} =
-,则顶点 (x, y) 与 边 (x, y+2) 之间有一条无向边。- 奇数 x, y 是 在 U_i \le x \le D_i - 2,\ L_i \le y \le R_i 和 S_{x+1,y} =
|,则顶点 (x, y) 与 边 (x+2, y) 之间有一条无向边。无向图 求 G 的连通分量的数量。
制約
- N 是一个整数
- 1 \le N \le 2000
- i 是奇数,
当j 为奇数时,
当 S_{i, j} =
o - i 是奇数,
当j 为偶数时, S_{i, j} =
-或 至少. - i 是偶数,j 为奇数时,
当 S_{i, j} =
|或 至少. - i 是偶数,j 为偶数时, S_{i, j} =
. - Q 是一个整数
- 1 \le Q \le 7000
- 1 \le U_i \le D_i \le 2N+1
- 1 \le L_i \le R_i \le 2N+1
- U_i, D_i, L_i, R_i 是奇数
入力
输入是按以下格式从标准输入给出的。
N
S_{1,1}S_{1,2}\cdotsS_{1,2N+1}
S_{2,1}S_{2,2}\cdotsS_{2,2N+1}
\vdots
S_{2N+1,1}S_{2N+1,2}\cdotsS_{2N+1,2N+1}
Q
U_1 D_1 L_1 R_1
U_2 D_2 L_2 R_2
\vdots
U_Q D_Q L_Q R_Q
出力
Q 行。 i=1,2,\dots, Q 关于 i 在线 i 个查询的答案。
入力例 1
3 o-o-o-o |.....| o-o.o.o |.|.... o-o.o-o ....|.| o.o-o-o 12 3 5 1 7 1 1 1 1 1 3 1 3 1 3 1 7 1 1 1 1 1 1 1 7 1 7 1 1 1 7 1 7 3 5 3 5 3 5 3 7 3 7 3 7 5 7 3 5
出力例 1
4 1 1 2 1 1 2 4 3 4 4 2
给定的网格如下所示: 第

1 个查询的答案如下图所示。 4 。 对于
