人们说:“岁月就像多米诺骨牌，一张接一张地倒下。”但是一年的时间能在网格里吗?我不这么想。
Limak是一只喜欢玩的小北极熊。他最近得到了一个有h行和w列的矩形网格。每个单元格都是一个正方形，要么是空的(用'.'表示)，要么是禁止的(用'#'表示)。
行从上到下编号为1到h。列从左到右编号为1到w。
此外，Limak有一张多米诺骨牌，他想把它放在网格里。一个多米诺骨牌将占据两个相邻的单元格，它们位于一行或一列中。相邻的两个单元格必须为空，并且必须位于网格内。
Limak需要更多的乐趣，因此他会考虑一些问题，如输入左上角和右下角的坐标，查询在选中的区域中，有多少种方法可以将一个多米诺骨牌放入所选矩形中?
输入的第一行包含两个整数h和w(1≤h,w≤500)——分别为行数和列数。
接下来的h行描述了一个网格。每一行包含一个长度为w的字符串。每个字符不是'。'或'#'−分别表示空单元格或禁止单元格。
下一行为单个整数q(1≤q≤100000)−查询次数。
接下来的每一行都包含四个整数r1i, c1i, r2i, c2i(1≤r1i≤r2i≤h,1≤c1i≤c2i≤w)−第i个查询。数字r1i和c1i分别表示矩形左上角单元格的行和列。数字r2i和c2i分别表示矩形右下单元格的行和列。
打印q个整数，第i个应该等于把一个多米诺骨牌放入第i个矩形的方法的数量。
5 8 ....#..# .#...... ##.#.... ##..#.## ........ 4 1 1 2 3 4 1 4 1 1 2 4 5 2 5 5 8
4 0 10 15
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
53 89 120 23 0 2
注意
下面的红框对应于第一个示例的第一个查询。多米诺骨牌可以通过 4 种可能的方式放置。
5 8
....#..#
.#......
##.#....
##..#.##
........
4
1 1 2 3
4 1 4 1
1 2 4 5
2 5 5 84
0
10
15