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 _i, c1 _i, r2 _i, c2 _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
....#..#
.#......
##.#....
##..#.##
........
4
1 1 2 3
4 1 4 1
1 2 4 5
2 5 5 8

output

4
0
10
15

input

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

output

53
89
120
23
0
2

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;
}