CF611C.New Year and Domino

They say "years are like dominoes, tumbling one after the other". But would a year fit into a grid? I don't think so.

Limak is a little polar bear who loves to play. He has recently got a rectangular grid with h rows and w columns. Each cell is a square, either empty (denoted by '.') or forbidden (denoted by '#'). Rows are numbered 1 through h from top to bottom. Columns are numbered 1 through w from left to right.

Also, Limak has a single domino. He wants to put it somewhere in a grid. A domino will occupy exactly two adjacent cells, located either in one row or in one column. Both adjacent cells must be empty and must be inside a grid.

Limak needs more fun and thus he is going to consider some queries. In each query he chooses some rectangle and wonders, how many way are there to put a single domino inside of the chosen rectangle?

人们常说：“岁月如多米诺骨牌，一个接一个地倾倒。”但一年能放进一个网格里吗？我想不能。

Limak 是一只可爱的小北极熊，他很喜欢玩耍。他最近得到了一个大小为 $h$ 行 $w$ 列的矩形网格。每个格子是一个正方形，要么为空（用 . 表示），要么为禁止放置（用 # 表示）。行从上到下编号为 $1$ 至 $h$，列从左到右编号为 $1$ 至 $w$。

此外，Limak 拥有一枚多米诺骨牌。他想将它放在网格中的某个位置。一枚多米诺骨牌恰好占据两个相邻的格子，这两个格子必须位于同一行或同一列。两个相邻格子都必须为空，且均需位于网格内部。

Limak 渴望更多乐趣，因此他将考虑若干查询。在每次查询中，他选定某个矩形区域，并思考：有多少种方式可将一枚多米诺骨牌完全放置于该选定矩形区域内？

The first line of the input contains two integers h and w (1 ≤ h, w ≤ 500) – the number of rows and the number of columns, respectively.

The next h lines describe a grid. Each line contains a string of the length w. Each character is either '.' or '#' — denoting an empty or forbidden cell, respectively.

The next line contains a single integer q (1 ≤ q ≤ 100 000) — the number of queries.

Each of the next q lines contains four integers r_1_i, c_1_i, r_2_i, c_2_i (1 ≤ r_1_i ≤ r_2_i ≤ h, 1 ≤ c_1_i ≤ c_2_i ≤ w) — the i-th query. Numbers r_1_i and c_1_i denote the row and the column (respectively) of the upper left cell of the rectangle. Numbers r_2_i and c_2_i denote the row and the column (respectively) of the bottom right cell of the rectangle.

输入的第一行包含两个整数 $h$ 和 $w$（$1 \leq h, w \leq 500$），分别表示网格的行数和列数。

接下来的 $h$ 行描述一个网格。每行包含一个长度为 $w$ 的字符串，其中每个字符为 . 或 #，分别表示空单元格或禁止通行的单元格。

接下来一行包含一个整数 $q$（$1 \leq q \leq 100\,000$），表示查询的数量。

接下来的 $q$ 行中，每行包含四个整数 $r_{1i}$、$c_{1i}$、$r_{2i}$、$c_{2i}$（$1 \leq r_{1i} \leq r_{2i} \leq h$，$1 \leq c_{1i} \leq c_{2i} \leq w$），表示第 $i$ 个查询。其中 $r_{1i}$ 和 $c_{1i}$ 分别表示矩形左上角单元格的行号与列号；$r_{2i}$ 和 $c_{2i}$ 分别表示矩形右下角单元格的行号与列号。

Print q integers, i-th should be equal to the number of ways to put a single domino inside the i-th rectangle.

输出 $q$ 个整数，其中第 $i$ 个整数应等于在第 $i$ 个矩形内放置一个骨牌（domino）的方法数。

A red frame below corresponds to the first query of the first sample. A domino can be placed in 4 possible ways.

下方的红色框对应第一个样例的第一个查询。多米诺骨牌有 4 种可能的放置方式。