← 返回题目列表

Codeforces · 611/C

C. 新年和多米诺骨牌

中文机器翻译题面 查看原题

他们说“岁月就像多米诺骨牌,一个接一个地翻倒”。但是一年适合一个网格吗?我不这么认为。

Limak 是一只喜欢玩耍的小北极熊。他最近得到了一个 h 行 w 列的矩形网格。每个单元格都是一个正方形,要么是空的(用“.”表示),要么是禁止的(用“#”表示)。行从上到下编号为 1 到 h。列从左到右编号为 1 到 w。

另外,Limak 有一个多米诺骨牌。他想把它放在网格中的某个地方。多米诺骨牌将恰好占据两个相邻的单元格,位于一行或一列。两个相邻的单元格必须为空并且必须位于网格内。

Limak 需要更多乐趣,因此他将考虑一些问题。在每个查询中,他都会选择一些矩形,并想知道有多少种方法可以将单个多米诺骨牌放在所选矩形内?

输入

输入的第一行包含两个整数 h 和 w (1 ≤ h, w ≤ 500) – 分别是行数和列数。

接下来的 h 行描述了一个网格。每行包含一个长度为 w 的字符串。每个字符都是“.”或“#”——分别表示空单元格或禁止单元格。

下一行包含一个整数 q (1 ≤ q ≤ 100 000) — 查询数。

接下来的 q 行包含四个整数 r1i、c1i、r2i、c2i (1 ≤ r1i ≤ r2i ≤ h, 1 ≤ c1i ≤ c2i ≤ w) — 第 i 个查询。数字 r1i 和 c1i 分别表示矩形左上单元格的行和列。数字 r2i 和 c2i 分别表示矩形右下单元格的行和列。

输出

打印 q 个整数,第 i 个应该等于在第 i 个矩形内放置单个多米诺骨牌的方式数。

示例

输入 #1

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

输出 #1

4
0
10
15

输入 #2

7 39
.......................................
.###..###..#..###.....###..###..#..###.
...#..#.#..#..#.........#..#.#..#..#...
.###..#.#..#..###.....###..#.#..#..###.
.#....#.#..#....#.....#....#.#..#..#.#.
.###..###..#..###.....###..###..#..###.
.......................................
6
1 1 3 20
2 10 6 30
2 10 7 30
2 2 7 7
1 7 7 7
1 8 7 8

输出 #2

53
89
120
23
0
2

注意

下面的红框对应于第一个样本的第一个查询。多米诺骨牌可以通过 4 种可能的方式放置。