CF611C New Year and Domino

人们常说“岁月如多米诺骨牌，一年接着一年倒下”。可是一年能放进一个网格里吗？我可不这么认为。 Limak 是一只喜欢玩耍的小北极熊。最近他得到了一个矩形网格，这个网格有 $h$ 行 $w$ 列。每个单元格是一个正方形，要么是空的（用 `.` 表示），要么是禁用的（用 `#` 表示）。行号从 $1$ 到 $h$，自上而下标号，列号从 $1$ 到 $w$，自左至右标号。 Limak 拥有唯一的一块多米诺骨牌。他想把它放在网格里的某个地方。多米诺骨牌恰好要占据两个相邻的单元格，这两个单元格要么在同一行上，要么在同一列上。并且，这两个单元格都必须是空的，并且都在网格内部。 为了获得更多乐趣，Limak 决定提出一些询问。每一次询问他会选择一个矩形区域，并想知道在这个矩形内可以以多少种方式放置唯一一块多米诺骨牌。

第一行包含两个整数 $h$ 和 $w$（$1 \leq h, w \leq 500$），表示网格的行数和列数。 接下来的 $h$ 行描述网格。每行包含一个长度为 $w$ 的字符串，每个字符要么是 `.`，要么是 `#`，分别表示空单元格或禁用单元格。 下一行包含一个整数 $q$（$1 \leq q \leq 100000$），表示询问的数量。 接下来的 $q$ 行，每行包含四个整数 $r1_i$，$c1_i$，$r2_i$，$c2_i$（$1 \leq r1_i \leq r2_i \leq h, 1 \leq c1_i \leq c2_i \leq w$），表示第 $i$ 个询问。$r1_i$ 和 $c1_i$ 指的是矩形左上角的行号和列号，$r2_i$ 和 $c2_i$ 指的是矩形右下角的行号和列号。

输出 $q$ 个整数，第 $i$ 个数为在第 $i$ 个矩形内能够放置一块多米诺骨牌的方案数。

下图红色边框对应第一个样例的第一个询问。在该矩形范围内，多米诺骨牌有 4 种不同的放法。  由 ChatGPT 5 翻译