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

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<=100000$ ) — 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.

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