# 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?

Input

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 r1 ic1 ir2 ic2 i (1 ≤ r1 i ≤ r2 i ≤ h, 1 ≤ c1 i ≤ c2 i ≤ w) — the i-th query. Numbers r1 i and c1 i denote the row and the column (respectively) of the upper left cell of the rectangle. Numbers r2 i and c2 i denote the row and the column (respectively) of the bottom right cell of the rectangle.

Output

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

Examples

input

5 8....#..#.#......##.#....##..#.##........41 1 2 34 1 4 11 2 4 52 5 5 8

output

401015

input

7 39........................................###..###..#..###.....###..###..#..###....#..#.#..#..#.........#..#.#..#..#....###..#.#..#..###.....###..#.#..#..###..#....#.#..#....#.....#....#.#..#..#.#..###..###..#..###.....###..###..#..###........................................61 1 3 202 10 6 302 10 7 302 2 7 71 7 7 71 8 7 8

output

53891202302

Note

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

Solution:

#include <bits/stdc++.h>

using namespace std;

const int N = 777;

int hor[N][N], ver[N][N];
char s[N][N];

int main() {
int h, w;
scanf("%d %d", &h, &w);
for (int i = 0; i < h; i++) {
scanf("%s", s[i]);
}
for (int i = 0; i <= h; i++) {
for (int j = 0; j <= w; j++) {
if (i == 0 || j == 0) {
ver[i][j] = 0;
} else {
ver[i][j] = ver[i - 1][j] + ver[i][j - 1] - ver[i - 1][j - 1];
if (i < h && s[i - 1][j - 1] == '.' && s[i][j - 1] == '.') {
ver[i][j]++;
}
}
if (i == 0 || j == 0) {
hor[i][j] = 0;
} else {
hor[i][j] = hor[i - 1][j] + hor[i][j - 1] - hor[i - 1][j - 1];
if (j < w && s[i - 1][j - 1] == '.' && s[i - 1][j] == '.') {
hor[i][j]++;
}
}
}
}
int tt;
scanf("%d", &tt);
while (tt--) {
int xa, ya, xb, yb;
scanf("%d %d %d %d", &xb, &yb, &xa, &ya);
int ans = 0;
ans += hor[xa][ya - 1] - hor[xb - 1][ya - 1] - hor[xa][yb - 1] + hor[xb - 1][yb - 1];
ans += ver[xa - 1][ya] - ver[xa - 1][yb - 1] - ver[xb - 1][ya] + ver[xb - 1][yb - 1];
printf("%d\n", ans);
}
return 0;
}