Broken Exit

The popular game "Broken Exits" is a puzzle game where the goal is to escape from a maze with the least number of moves. The maze consists of $N \times M$ squares and each square is assigned a row number and a column number. A square with row number $r$ and column number $c$ is denoted by ($r, c$). The top left corner of the square is occupied by square (0, 0) and the bottom right corner is occupied by square ($N-1, M-1$). Each square is assigned one of the following symbols:

.	Ground
E	Exit
#	Wall

In each play of the game, you start from the square designated for each play and try to reach the exit. Each exit can be reached from any square except walls. If the adjacent square above, below, right or left of the square you are in is the ground or an exit, you can move to that square. However, you cannot move to a square without a square.

A maze may contain two or more exits, one of which is broken. Which exit is broken is specified for each play. The play ends when you reach an exit that is not broken. If an exit is broken, you can still move to that exit square, but it does not end the game.

Write a program which reads a maze and the information for each play and outputs the minimum number of moves until each play is completed.

Input

The input is given in the following form.

$N$ $M$
$row_1$
$row_2$
:
$row_N$
$P$
$sr_1$ $sc_1$ $br_1$ $bc_1$
$sr_2$ $sc_2$ $br_2$ $bc_2$
:
$sr_P$ $sc_P$ $br_P$ $bc_P$

In the first line, two integers $N$ ($2 \leq N \leq 1,000$) and $M$ ($2 \leq M \leq 1,000$) are given to represent the size of a maze. A string $row_i$ is given in the next $N$ lines to represent the information of the $i$-th square from the top. $row_i$ is a string of length $M$ and the $j$-th character represents the symbol of square ($i-1,j-1$). In the following line, the number of plays $P$ ($1 \leq P \leq 100,000$) is given. The subsequent $P$ lines give the integers $sr_i$,$sc_i$,$br_i$,$bc_i$ ($0 \leq sr_i,br_i < N, 0 \leq sc_i, bc_i < M$) that represent the starting ground square ($sr_i, sc_i$) and the broken exit square ($br_i, bc_i$) specified in each play.

Output

The output is $P$ rows. Output the minimum number of moves for each play in a line.

Sample Input and Output

Sample Input

4 5
.....
.#.#E
..##.
.E...
3
0 0 3 1
1 2 3 1
1 2 1 4

Sample Output

5
4
7

 

---