I found an interesting problem on https://codeforces.com/problemset/problem/611/C:
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...

I tried it in Python, but could not do it. Can you solve it?
h, w = list(map(int, input().split()))
field = [[c == "." for c in input()] + [False] for i in range(h)]
field.append([False] * (w + 1))

subVerts = [[0] * (w + 1) for i in range(h + 1)]
subHoriz = [[0] * (w + 1) for i in range(h + 1)]

for y in range(h):
    subVerts[y][0] = 0
    subHoriz[y][0] = 0

for x in range(w):
    subHoriz[0][x] = 0
    subVerts[0][x] = 0

for y in range(h):
    for x in range(w):
        subVerts[y + 1][x + 1] = subVerts[y + 1][x] + subVerts[y][x + 1] - subVerts[y][x]
        if field[y][x] and field[y - 1][x]:
            subVerts[y + 1][x + 1] += 1
        
        subHoriz[y + 1][x + 1] = subHoriz[y + 1][x] + subHoriz[y][x + 1] - subHoriz[y][x]
        if field[y][x] and field[y][x - 1]:
            subHoriz[y + 1][x + 1] += 1



q = int(input())
for i in range(q):
    y1, x1, y2, x2 = [int(x) - 1 for x in input().split()]
    ansHoriz = subHoriz[y2 + 1][x2 + 1] - subHoriz[y1][x2 + 1] - subHoriz[y2 + 1][x1 + 1] + subHoriz[y1][x1 + 1]
    ansVerts = subVerts[y2 + 1][x2 + 1] - subVerts[y1 + 1][x2 + 1] - subVerts[y2 + 1][x1] + subVerts[y1 + 1][x1]
    print(ansHoriz + ansVerts)