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. [Image]

Difficulty: interview

Starter code:

Solutions:
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)


#!/usr/bin/env python3

def string2d(arr):
    return ('\n'.join(' '.join(map(str, row)) for row in arr))

H, W = list(map(int, input().split()))
grid = [[c == '.' for c in input()] for i in range(H)]

blah1 = [[0 for j in range(W)] for i in range(H)]  # horizontal
blah2 = [[0 for j in range(W)] for i in range(H)]  # vertical

for i in range(H):
    for j in range(W):
        if not grid[i][j]:
            continue
        if j+1 < W and grid[i][j+1]:
            blah1[i][j] = 1
        if i+1 < H and grid[i+1][j]:
            blah2[i][j] = 1

# prefix sums
pref1 = [[0 for j in range(W+1)] for i in range(H+1)]
pref2 = [[0 for j in range(W+1)] for i in range(H+1)]

for i in range(1, H+1):
    for j in range(1, W+1):
        pref1[i][j] = pref1[i-1][j] + blah1[i-1][j-1]
        pref2[i][j] = pref2[i-1][j] + blah2[i-1][j-1]
for i in range(1, H+1):
    for j in range(1, W+1):
        pref1[i][j] += pref1[i][j-1]
        pref2[i][j] += pref2[i][j-1]

#print('blah:')
#print(string2d(blah1), '--', string2d(blah2), sep='\n')
#print('pref:')
#print(string2d(pref1), '--', string2d(pref2), sep='\n')

Q = int(input())
for q in range(Q):
    r1, c1, r2, c2 = list(map(int, input().split()))
    one = pref1[r2][c2-1] - pref1[r2][c1-1] - pref1[r1-1][c2-1] + pref1[r1-1][c1-1]
    two = pref2[r2-1][c2] - pref2[r2-1][c1-1] - pref2[r1-1][c2] + pref2[r1-1][c1-1]
    #print('one:', pref1[r2][c2-1], '-', pref1[r1-1][c1-1], '(%d %d)' % (r2, c2-1))
    #print('two:', pref2[r2-1][c2], '-', pref2[r1-1][c1-1], '(%d %d)' % (r2-1, c2))
    #print('result:', one, '+', two, '=', one+two)
    print(one + two)


def transpose(grid):
    return [[grid[y][x] for y in range(len(grid))] for x in range(len(grid[0]))]

def preprocess(grid):
    st1 = [[x >= 1 and grid[y][x-1] == grid[y][x] == '.'
            for x in range(len(grid[0]))]
           for y in range(len(grid))]
    st2 = [[0 for x in range(len(st1[0]))] for y in range(len(st1))]
    for y in range(len(st1)):
        for x in range(len(st1[0])):
            st2[y][x] = ((st2[y-1][x] if y >= 1 else 0) +
                         (st2[y][x-1] if x >= 1 else 0) -
                         (st2[y-1][x-1] if y >= 1 and x >= 1 else 0) +
                         int(st1[y][x]))
    return st2

import pprint

h, w = [int(x) for x in input().split()]
grid = [input() for y in range(h)]
pre, pre2 = preprocess(grid), transpose(preprocess(transpose(grid)))
#print(len(pre), len(pre[0]), len(pre2), len(pre2[0]))
#pprint.pprint(pre)
#pprint.pprint(pre2)
q = int(input())
for qi in range(q):
    r1, c1, r2, c2 = [int(x) for x in input().split()]
    r1, c1, r2, c2 = r1-1, c1-1, r2-1, c2-1
    """val = (pre[r2][c2] +
           (pre[r1-1][c1-1] if r1 >= 1 and c1 >= 1 else 0) -
           (pre[r2][c1-1] if c1 >= 1 else 0) -
           (pre[r1-1][c2] if r1 >= 1 else 0) +
           pre2[r2][c2] +
           (pre2[r1-1][c1-1] if r1 >= 1 and c1 >= 1 else 0) -
           (pre2[r2][c1-1] if c1 >= 1 else 0) -
           (pre2[r1-1][c2] if r1 >= 1 else 0))
    """
    """val = (pre[r2][c2] - pre[r2][c1] - pre[r1][c2] + pre[r1][c1] +
           pre2[r2][c2] - pre2[r2][c1] - pre2[r1][c2] + pre2[r1][c1])"""
    val = (pre[r2][c2] +
           (pre[r1-1][c1] if r1 >= 1 else 0) -
           (pre[r2][c1] if c1 >= 0 else 0) -
           (pre[r1-1][c2] if r1 >= 1 else 0) +
           pre2[r2][c2] +
           (pre2[r1][c1-1] if c1 >= 1 else 0) -
           (pre2[r2][c1-1] if c1 >= 1 else 0) -
           (pre2[r1][c2] if r1 >= 0 else 0))
    """print(val, pre[r2][c2] +
           (pre[r1-1][c1] if r1 >= 1 else 0) -
           (pre[r2][c1] if c1 >= 0 else 0) -
           (pre[r1-1][c2] if r1 >= 1 else 0),
          pre2[r2][c2] +
           (pre2[r1][c1-1] if c1 >= 1 else 0) -
           (pre2[r2][c1-1] if c1 >= 1 else 0) -
           (pre2[r1][c2] if r1 >= 0 else 0), r1, c1, r2, c2)"""
    print(val)


h, w = map(int, input().split())
field = [input() for i in range(h)]
q = int(input())

inrow = [[0] * (w + 1) for i in range(h + 1)]  # [row][end_col]
for i in range(h):
    sum = 0
    for j in range(1, w):
        if field[i][j] == field[i][j - 1] == ".":
            sum += 1
        inrow[i][j] = sum
incol = [[0] * (h + 1) for i in range(w + 1)]  # [col][start_row]
for j in range(w):
    sum = 0
    for i in range(1, h):
        if field[i][j] == field[i - 1][j] == ".":
            sum += 1
        incol[j][i] = sum
suminrows = [[0] * (w + 1) for i in range(h + 1)]  # [end_row][end_col]
for j in range(w):
    sum = 0
    for i in range(h):
        sum += inrow[i][j]
        suminrows[i][j] = sum
sumincols = [[0] * (h + 1) for i in range(w + 1)]  # [end_col][end_row]
for i in range(h):
    sum = 0
    for j in range(w):
        sum += incol[j][i]
        sumincols[j][i] = sum
for test in range(q):
    r1, c1, r2, c2 = map(int, input().split())
    r1, c1, r2, c2 = r1-1, c1-1, r2-1, c2-1
    ans = 0
    ans += (suminrows[r2][c2] - suminrows[r1 - 1][c2]) - (suminrows[r2][c1] - suminrows[r1 - 1][c1])
    ans += (sumincols[c2][r2] - sumincols[c1 - 1][r2]) - (sumincols[c2][r1] - sumincols[c1 - 1][r1])
    print(ans)

__author__ = 'Utena'
h,w=map(int,input().split())
q=[[0]*w for i in range(h)]
for i1 in range(h):
    n0=input()
    for i in range(w):
        if n0[i]=='#':
            q[i1][i]=1
a=[[0]*w for i2 in range(h+1)]
b=[[0]*(w+1) for i3 in range(h)]
for i in range(h):
    for j in range(w-1):
        if q[i][j]==q[i][j+1]==0:
            a[i+1][j+1]=a[i+1][j]+1
        else:
            a[i+1][j+1]=a[i+1][j]
for i in range(1,h+1):
    for j in range(w):
        a[i][j]+=a[i-1][j]
for i in range(h-1):
    for j in range(w):
        if q[i][j]==q[i+1][j]==0:
            b[i+1][j+1]=b[i][j+1]+1
        else:
            b[i+1][j+1]=b[i][j+1]
for i in range(h):
    for j in range(1,w+1):
        b[i][j]+=b[i][j-1]
n=int(input())
for k in range(n):
    r1,c1,r2,c2=list(map(int,input().split()))
    t=a[r2][c2-1]-a[r2][c1-1]-a[r1-1][c2-1]+a[r1-1][c1-1]+b[r2-1][c2]-b[r1-1][c2]-b[r2-1][c1-1]+b[r1-1][c1-1]
    print(t)

h, w = list(map(int, input().split()))
t = []
for i in range(h):
    lis = input()
    t.append(lis)
a = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    maxi = 0
    for j in range(1, w):
        if t[i][j] == '.' == t[i][j - 1]:
            a[i][j] = maxi + 1
            maxi = max(maxi, a[i][j])
        else:
            a[i][j] = maxi
d = [[0 for i in range(w)] for j in range(h)]
for i in range(w):
    d[0][i] = a[0][i]
for i in range(1, h):
    for j in range(w):
        d[i][j] = d[i - 1][j] + a[i][j]

a = [[0 for i in range(w)] for j in range(h)]
for j in range(w):
    maxi = 0
    for i in range(1, h):
        if t[i][j] == '.' == t[i - 1][j]:
            a[i][j] = maxi + 1
            maxi = max(maxi, a[i][j])
        else:
            a[i][j] = maxi
d1 = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    d1[i][0] = a[i][0]
for j in range(1, w):
    for i in range(h):
        d1[i][j] = a[i][j] + d1[i][j - 1]
q = int(input())
for i in range(q):
    r1, c1, r2, c2 = list(map(int, input().split()))
    r1 -= 1
    c1 -= 1
    r2 -= 1
    c2 -= 1
    if r1 == 0 and c1 == 0:
        print(d[r2][c2] + d1[r2][c2])
    elif r1 == 0:
        print(d[r2][c2]+d1[r2][c2]-d[r2][c1]-d1[r2][c1 - 1])
    elif c1 == 0:
        print(d[r2][c2] + d1[r2][c2] - d[r1 - 1][c2] - d1[r1][c2])
    else:
        print(d[r2][c2] + d1[r2][c2] - d[r1-1][c2] - d1[r1][c2] - d[r2][c1] - d1[r2][c1 - 1] + d[r1-1][c1] + d1[r1][c1-1])




n , m = list(map(int, input().split()))
s = ['#' * (m+2)]
for i in range(n):
    s += ['#'+input()+'#']
s+= ['#' * (m+2)] 
u = [[0 for i in range(m+2)] for j in range(n+2)]
r = [[0 for i in range(m+2)] for j in range(n+2)]
for i in range(1, n+1):
    for j in range(1, m+1):
        if s[i][j] == '.':
            if s[i+1][j] == '.':
                u[i][j] = 1
            if s[i][j+1] == '.':
                r[i][j] = 1
        u[i][j]+= u[i-1][j]+u[i][j-1]-u[i-1][j-1]
        r[i][j]+= r[i-1][j]+r[i][j-1]-r[i-1][j-1]
q = int(input())
for i in range(q):
    A = 0
    x, y, a, b = list(map(int, input().split()))
    if x == a and y == b:
        A = 0
    else:
        A += r[a][b-1]-r[x-1][b-1]-r[a][y-1]+r[x-1][y-1]
        A += u[a-1][b]-u[x-1][b]-u[a-1][y-1]+u[x-1][y-1]
    print(A)



from itertools import accumulate 
import math
import bisect

def list_sum(L1, L2):
    return [L1[i] + L2[i] for i in range(len(L1))]

h, w = [int(x) for x in input().split()]
M = []
for i in range(h):
    M.append([1 if c == '.' else 0 for c in input().rstrip()])

H = [[0]+list(accumulate(M[i][j] and M[i][j+1] for j in range(w-1))) for i in range(h)]
V = [[0]+list(accumulate(M[i][j] and M[i+1][j] for i in range(h-1))) for j in range(w)]

Hsum = list(accumulate(H, list_sum))
Vsum = list(accumulate(V, list_sum))

def can(a, b):
    return Hsum[a][b] + Vsum[b][a]

def query(a1, b1, a2, b2):
    return (can(a2, b2) + can(a1, b1) - can(a1, b2) - can(a2, b1) +
            H[a1][b2] - H[a1][b1] + V[b1][a2] - V[b1][a1])

q = int(input())
for i in range(q):
    a1, b1, a2, b2 = [int(x)-1 for x in input().split()]
    print(query(a1, b1, a2, b2))


read = lambda: list(map(int, input().split()))
h, w = read()
a = [input() for i in range(h)]
N = 501
vr = [[0] * N for i in range(N)]
hr = [[0] * N for i in range(N)]
for i in range(h):
    for j in range(w):
        vr[j + 1][i + 1] = vr[j][i + 1] + vr[j + 1][i] - vr[j][i]
        hr[j + 1][i + 1] = hr[j][i + 1] + hr[j + 1][i] - hr[j][i]
        if a[i][j] == '#': continue
        if i != h - 1 and a[i + 1][j] == '.': vr[j + 1][i + 1] += 1
        if j != w - 1 and a[i][j + 1] == '.': hr[j + 1][i + 1] += 1
q = int(input())
for i in range(q):
    r1, c1, r2, c2 = read()
    p1 = hr[c2 - 1][r2] - hr[c1 - 1][r2] - hr[c2 - 1][r1 - 1] + hr[c1 - 1][r1 - 1]
    p2 = vr[c2][r2 - 1] - vr[c1 - 1][r2 - 1] - vr[c2][r1 - 1] + vr[c1 - 1][r1 - 1]
    ans = p1 + p2
    print(ans)


h, w = list(map(int, input().split()))
mp = []
mp.append(list("#" * (w + 2)))
for i in range(h):
    mp.append(list(input()))
    mp[i + 1].insert(0, "#")
    mp[i + 1].append("#")
mp.append(list("#" * (w + 2)))
mpV = []
mpH = []
mpV.append([])
mpH.append([])
for i in range(w + 2):
    mpV[0].append(0)
    mpH[0].append(0)

for i in range(1, h + 2):
    mpV.append([])
    mpH.append([])
    mpV[i].append(0)
    mpH[i].append(0)
    for j in range(1, w + 2):
        mpV[i].append(mpV[i][j - 1] + mpV[i - 1][j] - mpV[i - 1][j - 1] + (
            1 if mp[i][j] == "." and mp[i + 1][j] == "." else 0))
        mpH[i].append(mpH[i][j - 1] + mpH[i - 1][j] - mpH[i - 1][j - 1] + (
            1 if mp[i][j] == "." and mp[i][j + 1] == "." else 0))
anc = []
n = int(input())
for k in range(n):
    y0, x0, y1, x1 = list(map(int, input().split()))
    A = mpV[y0 - 1][x0 - 1]+mpV[y1-1][x1]-mpV[y1-1][x0-1]-mpV[y0-1][x1]
    A += mpH[y0 - 1][x0 - 1]+mpH[y1][x1-1]-mpH[y1][x0-1]-mpH[y0-1][x1-1]
    anc.append(A)
for k in range(n):
    print(anc[k])

h, w = list(map(int, input().split()))
grid = (h + 1) * [ None ]
grid[0] = (w + 1) * '#'
for r in range(1, h + 1):
    grid[r] = '#' + input().strip()

rt = [ [ 0 for c in range(w + 1) ] for r in range(h + 1) ]
for r in range(1, h + 1):
    for c in range(1, w + 1):
        if '.' == grid[r][c] == grid[r][c - 1]:
            delta = 1
        else:
            delta = 0
        rt[r][c] = rt[r][c - 1] + delta
    for c in range(1, w + 1):
        rt[r][c] += rt[r - 1][c]
ct = [ [ 0 for c in range(w + 1) ] for r in range(h + 1) ]
for c in range(1, w + 1):
    for r in range(1, h + 1):
        if '.' == grid[r][c] == grid[r - 1][c]:
            delta = 1
        else:
            delta = 0
        ct[r][c] = ct[r - 1][c] + delta
    for r in range(1, h + 1):
        ct[r][c] += ct[r][c - 1]

debug = False
if debug:
    print()
    for r in range(1, h + 1):
        print(grid[r][1:])
        print(rt[r][1:])
    print()
    for c in range(1, w + 1):
        print(''.join([ grid[r][c] for r in range(1, h + 1) ]))
        print([ ct[r][c] for r in range(1, h + 1) ])
    print()

q = int(input())
for i in range(q):
    r, c, R, C = list(map(int, input().split()))
    if debug:
        print((rt[R][C], -rt[R][c], -rt[r - 1][C], rt[r - 1][c], '\n',
              ct[R][C], -ct[r][C], -ct[R][c - 1], ct[r][c - 1]))
    x = rt[R][C] - rt[R][c] - rt[r - 1][C] + rt[r - 1][c] + \
        ct[R][C] - ct[r][C] - ct[R][c - 1] + ct[r][c - 1]
    print(x)



def solve(h, w, board, queries):

    def get_horiz(h, w, board):
        horiz = [[None] * w for _ in range(h)]
        for i in range(w):
            for j in range(h):
                if i == 0:
                    horiz[j][i] = 0
                    continue
                current = 1 if (board[j][i] == '.' and board[j][i-1] == '.') else 0
                if j == 0:
                    horiz[j][i] = horiz[j][i-1] + current
                else:
                    current = 1 if (board[j][i] == '.' and board[j][i-1] == '.') else 0
                    horiz[j][i] = horiz[j][i-1] + horiz[j-1][i] - horiz[j-1][i-1] + current
        return horiz

    trans = [[None] * h for _ in range(w)]
    for i in range(w):
        for j in range(h):
            trans[i][j] = board[j][i]

    horiz = get_horiz(h, w, board)
    vert = get_horiz(w, h, trans)

    def query(r1, c1, r2, c2):
        r1 -= 1
        c1 -= 1
        r2 -= 1
        c2 -= 1
        acum = 0
        for rr1, rr2, cc1, cc2, horizvert in [(r1, r2, c1, c2, horiz), (c1, c2, r1, r2, vert)]:
            base = horizvert[rr2][cc2]
            if rr1 > 0:
                base -= horizvert[rr1 - 1][cc2]
                base += horizvert[rr1 - 1][cc1]
            base -= horizvert[rr2][cc1]
            acum += base
        return acum

    #print(get_horiz(h, w, board))
    #print(query(1,2,4,5))
    res = []
    for q in queries:
        res.append(query(*q))
    return res

h, w = tuple(map(int, input().split()))
board = []
for _ in range(h):
    board.append(input())
qnum = int(input())
queries = []
for _ in range(qnum):
    queries.append(tuple(map(int, input().split())))
res = solve(h, w, board, queries)
for r in res:
    print(r)


n, m = list(map(int, input().split()))
a = [' ' + input() for i in range(n)]
a = [' '*(m+1)] + a
q = int(input())

col = [[0 for i in range(m+1)] for i in range(n+1)]
row = [[0 for i in range(m+1)] for i in range(n+1)]

for i in range(1, n+1):
    for j in range(1, m+1):
        col[i][j] = col[i-1][j] + col[i][j-1] - col[i-1][j-1] + (a[i][j] == '.' and a[i-1][j] == '.')
        row[i][j] = row[i-1][j] + row[i][j-1] - row[i-1][j-1] + (a[i][j] == '.' and a[i][j-1] == '.')

for i in range(q):
    r1, c1, r2, c2 = list(map(int, input().split()))
    print((col[r2][c2] - col[r1][c2] - col[r2][c1-1] + col[r1][c1-1] \
        + row[r2][c2] - row[r2][c1] - row[r1-1][c2] + row[r1-1][c1]))


H, W = list(map(int, input().split()))
grid = ["|" * (W+1)] + ["|" + input() for _ in range(H)]
Q = int(input())

hor = [[0 for _ in range(W+1)] for _ in range(H+1)]
ver = [[0 for _ in range(W+1)] for _ in range(H+1)]

for i in range(1, H+1):
    for j in range(1, W+1):
        hor[i][j] = hor[i-1][j] + hor[i][j-1] - hor[i-1][j-1]
        ver[i][j] = ver[i-1][j] + ver[i][j-1] - ver[i-1][j-1]
        if grid[i][j-1] == "." and grid[i][j] == ".":
            hor[i][j] += 1
        if grid[i-1][j] == "." and grid[i][j] == ".":
            ver[i][j] += 1

for _ in range(Q):
    r1, c1, r2, c2 = list(map(int, input().split()))

    answer = 0
    answer += ver[r2][c2] - ver[r1][c2] - ver[r2][c1-1] + ver[r1][c1-1]
    answer += hor[r2][c2] - hor[r2][c1] - hor[r1-1][c2] + hor[r1-1][c1]

    print(answer)


n, m = map(int, input().split())
li = [' '*(m+1)]+[' '+input() for _ in range(n)]
r,c = [[0 for i in range(m+1)] for i in range(n+1)],[[0 for i in range(m+1)] for i in range(n+1)]
q = int(input())
for i in range(1,n+1):
	for j in range(1,m+1):
		r[i][j]=r[i-1][j]+r[i][j-1]-r[i-1][j-1]+(li[i][j]=='.' and li[i][j-1]=='.')
		c[i][j]=c[i-1][j]+c[i][j-1]-c[i-1][j-1]+(li[i][j]=='.' and li[i-1][j]=='.')
for _ in range(q):
	r1,c1,r2,c2 = map(int,input().split())
	print (c[r2][c2]-c[r1][c2]-c[r2][c1-1]+c[r1][c1-1]+r[r2][c2]-r[r2][c1]-r[r1-1][c2]+r[r1-1][c1])

def main():
    h, w = list(map(int, input().split()))
    l = [[c == '.' for c in input()] for _ in range(h)]
    ver = [[0] * (w + 1) for _ in range(h + 1)]
    for y, aa, bb, l0, l1 in zip(list(range(h - 1)), ver, ver[1:], l, l[1:]):
        for x in range(w):
            bb[x + 1] = (l0[x] and l1[x]) + bb[x] + aa[x + 1] - aa[x]
    hor = [[0] * (w + 1) for _ in range(h + 1)]
    for y, aa, bb, l0 in zip(list(range(h)), hor, hor[1:], l):
        for x in range(w - 1):
            bb[x + 1] = (l0[x] and l0[x + 1]) + bb[x] + aa[x + 1] - aa[x]
    res = []
    for _ in range(int(input())):
        r1, c1, r2, c2 = list(map(int, input().split()))
        r1 -= 1
        c1 -= 1
        res.append(str(ver[r2 - 1][c2] - ver[r1][c2] - ver[r2 - 1][c1] + ver[r1][c1] +
                       hor[r2][c2 - 1] - hor[r1][c2 - 1] - hor[r2][c1] + hor[r1][c1]))
    print('\n'.join(res))


def __starting_point():
    main()

__starting_point()

#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2016 missingdays <missingdays@missingdays>
#
# Distributed under terms of the MIT license.

"""

"""
def read_list():
    return [int(i) for i in input().split()]
def new_list(n):
    return [0 for i in range(n)]
def new_matrix(n, m=0):
    return [[0 for i in range(m)] for i in range(n)]


m = 2005

h, w = read_list()

d = []
for i in range(h):
    d.append(input())

ver = new_matrix(m, m)
hor = new_matrix(m, m)

for j in range(h):
    for i in range(w):
        hor[i+1][j+1] = hor[i+1][j] + hor[i][j+1] - hor[i][j]
        ver[i+1][j+1] = ver[i+1][j] + ver[i][j+1] - ver[i][j]

        if d[j][i] == ".":
            if i < w-1 and d[j][i+1] == ".":
                hor[i+1][j+1] += 1
            if j < h-1 and d[j+1][i] == ".":
                ver[i+1][j+1] += 1


n = int(input())

for i in range(n):
    y1, x1, y2, x2 = read_list()

    x1 -= 1
    y1 -= 1

    answ = 0
    answ += (hor[x2-1][y2] - hor[x1][y2] - hor[x2-1][y1] + hor[x1][y1])
    answ += (ver[x2][y2-1] - ver[x1][y2-1] - ver[x2][y1] + ver[x1][y1])

    print(answ)


#!/usr/bin/env python3
import itertools, functools, math

def II(r1, c1, r2, c2, table):
    if r1 > r2:
        return 0
    if c1 > c2:
        return 0
    res = table[r2][c2]
    if r1:
        res -= table[r1-1][c2]
    if c1:
        res -= table[r2][c1-1]
    if r1 and c1:
        res += table[r1-1][c1-1]
    return res


def solve():
    h, w = list(map(int, input().split()))
    grid = [input() for _ in range(h)]

    row = [[0]*w for _ in range(h)]
    col = [[0]*w for _ in range(h)]

    for i in range(h):
        col_prev = 0
        row_prev = 0
        for j in range(w):
            row[i][j] = row_prev
            col[i][j] = col_prev
            if i:
                row[i][j] += row[i-1][j]
                col[i][j] += col[i-1][j]

            if grid[i][j] == '#':
                continue

            if i+1 < h and grid[i+1][j] != '#':
                row[i][j] += 1
                row_prev += 1
            if j+1 < w and grid[i][j+1] != '#':
                col[i][j] += 1
                col_prev += 1

    q = int(input())
    for _ in range(q):
        r1, c1, r2, c2 = list(map(int, input().split()))
        r1 -= 1
        c1 -= 1
        r2 -= 1
        c2 -= 1
        print(II(r1, c1, r2-1, c2, row) + II(r1, c1, r2, c2-1, col))


def __starting_point():
    solve()


__starting_point()

h,w = [int(i) for i in input().split()]
maxx = 2005
ver = [[0]*maxx for j in range(maxx)]
hor = [[0]*maxx for j in range(maxx)]
s = []
for i in range(h):
    s.append(input())

for x in range(h):
    for y in range(w):
        hor[x+1][y+1] = hor[x][y+1]+hor[x+1][y]-hor[x][y]
        ver[x+1][y+1] = ver[x][y+1]+ver[x+1][y]-ver[x][y]
        if (s[x][y]!='.'):continue
        if (y!=w-1 and s[x][y+1]=='.'): hor[x+1][y+1]+=1
        if (x!=h-1 and s[x+1][y]=='.'): ver[x+1][y+1]+=1

q = int(input())
ans = []
#print(hor[1][1])
print()
for _ in range(q):
    x,y,x1,y1 = [int(i) for i in input().split()]
    a = 0
    a+=hor[x1][y1-1]-hor[x1][y-1]-hor[x-1][y1-1]+hor[x-1][y-1]
    a+=ver[x1-1][y1]-ver[x1-1][y-1]-ver[x-1][y1]+ver[x-1][y-1]
    ans.append(a)
for i in ans:
    print(i)

h, w = (int(x) for x in input().split())
a = [[x != '.' for x in input()] for _ in range(h)]

def build(f):
    d = [[0 for _ in range(w + 1)]]
    for r in range(h):
        d.append([0])
        for c in range(w):
            d[-1].append(d[-2][c + 1] + d[-1][c] - d[-2][c] + f(r, c))
    return d

ver = build(lambda r, c: not a[r][c] and r < h - 1 and not a[r + 1][c])
hor = build(lambda r, c: not a[r][c] and c < w - 1 and not a[r][c + 1])

for _ in range(int(input())):
    r1, c1, r2, c2 = (int(x) for x in input().split())
    s = ver[r2 - 1][c2] - ver[r1 - 1][c2] - ver[r2 - 1][c1 - 1] + ver[r1 - 1][c1 - 1]
    s += hor[r2][c2 - 1] - hor[r1 - 1][c2 - 1] - hor[r2][c1 - 1] + hor[r1 - 1][c1 - 1]
    print(s)


# Description of the problem can be found at http://codeforces.com/problemset/problem/611/C

read = lambda: map(int, input().split())
h, w = read()
a = [input() for i in range(h)]
N = 501
vr = [[0] * N for i in range(N)]
hr = [[0] * N for i in range(N)]
for i in range(h):
    for j in range(w):
        vr[j + 1][i + 1] = vr[j][i + 1] + vr[j + 1][i] - vr[j][i]
        hr[j + 1][i + 1] = hr[j][i + 1] + hr[j + 1][i] - hr[j][i]
        if a[i][j] == '#': continue
        if i != h - 1 and a[i + 1][j] == '.': vr[j + 1][i + 1] += 1
        if j != w - 1 and a[i][j + 1] == '.': hr[j + 1][i + 1] += 1
q = int(input())
for i in range(q):
    r1, c1, r2, c2 = read()
    p1 = hr[c2 - 1][r2] - hr[c1 - 1][r2] - hr[c2 - 1][r1 - 1] + hr[c1 - 1][r1 - 1]
    p2 = vr[c2][r2 - 1] - vr[c1 - 1][r2 - 1] - vr[c2][r1 - 1] + vr[c1 - 1][r1 - 1]
    ans = p1 + p2
    print(ans)

n, m = map(int, input().split())
li = [' '*(m+1)]+[' '+input() for _ in range(n)]
r,c = [[0 for i in range(m+1)] for i in range(n+1)],[[0 for i in range(m+1)] for i in range(n+1)]
q = int(input())
for i in range(1,n+1):
	for j in range(1,m+1):
		r[i][j]=r[i-1][j]+r[i][j-1]-r[i-1][j-1]+(li[i][j]=='.' and li[i][j-1]=='.')
		c[i][j]=c[i-1][j]+c[i][j-1]-c[i-1][j-1]+(li[i][j]=='.' and li[i-1][j]=='.')
for _ in range(q):
	r1,c1,r2,c2 = map(int,input().split())
	print (c[r2][c2]-c[r1][c2]-c[r2][c1-1]+c[r1][c1-1]+r[r2][c2]-r[r2][c1]-r[r1-1][c2]+r[r1-1][c1])

line = input().split()
h, w = int(line[0]), int(line[1])
grid = []
for i in range(0, h):
	line = input()
	grid.append(line)
q = int(input().split()[0])
dp = [[[0 for z in range(0,2)] for x in range(w)] for y in range(h)]
for i in range(0, h):
	for j in range(0, w):
		dp[i][j][0] += (dp[i-1][j][0] if i > 0 else 0) + (dp[i][j-1][0] if j > 0 else 0) - (dp[i-1][j-1][0] if i > 0 and j > 0 else 0)
		dp[i][j][1] += (dp[i-1][j][1] if i > 0 else 0) + (dp[i][j-1][1] if j > 0 else 0) - (dp[i-1][j-1][1] if i > 0 and j > 0 else 0)
		dp[i][j][0] += (1 if i > 0 and grid[i][j] == '.' and grid[i-1][j] == '.' else 0)
		dp[i][j][1] += (1 if j > 0 and grid[i][j] == '.' and grid[i][j-1] == '.' else 0)
#print(dp[h-1][w-1])
while(q > 0):
	line = input().split()
	r1, c1, r2, c2 = int(line[0]), int(line[1]), int(line[2]), int(line[3])
	r1 -= 1
	c1 -= 1
	r2 -= 1
	c2 -= 1
	ans = 0
	ans += dp[r2][c2][0] + dp[r2][c2][1]
	ans -= (dp[r1-1][c2][0] + dp[r1-1][c2][1]) if r1 > 0 else 0
	ans -= (dp[r2][c1-1][0] + dp[r2][c1-1][1]) if c1 > 0 else 0
	ans += (dp[r1-1][c1-1][0] + dp[r1-1][c1-1][1]) if r1 > 0 and c1 > 0 else 0
	ans -= dp[r1][c2][0] - (dp[r1-1][c2][0] if r1 > 0 else 0) - (dp[r1][c1-1][0] if c1 > 0 else 0) + (dp[r1-1][c1-1][0] if c1 > 0 and r1 > 0 else 0)
	ans -= dp[r2][c1][1] - (dp[r2][c1-1][1] if c1 > 0 else 0) - (dp[r1-1][c1][1] if r1 > 0 else 0) + (dp[r1-1][c1-1][1] if c1 > 0 and r1 > 0 else 0)
	print(ans)
	#print(dp[r2][c2] - (dp[r1-1][c2] if r1 > 0 else 0) - (dp[r2][c1-1] if c1 > 0 else 0) + (dp[r1-1][c1-1] if r1 > 0 and c1 > 0 else 0))
	q -= 1