Good Bye 2015 |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

dp

implementation

*1500

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. New Year and Domino

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThey 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 *r*1_{i}, *c*1_{i}, *r*2_{i}, *c*2_{i} (1 ≤ *r*1_{i} ≤ *r*2_{i} ≤ *h*, 1 ≤ *c*1_{i} ≤ *c*2_{i} ≤ *w*) — the *i*-th query. Numbers *r*1_{i} and *c*1_{i} denote the row and the column (respectively) of the upper left cell of the rectangle. Numbers *r*2_{i} and *c*2_{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.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/31/2023 22:06:04 (l1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|