Cerință

Se dă o hartă de $N \times N$ care conține spații libere (notate cu .) și spații ocupate (notate cu #). Să se răspundă la $Q$ interogări de forma $i_1\ j_1\ i_2\ j_2$, unde se dorește să se afle distanța minimă de la celula $(i_1, j_1)$ la celula $(i_2, j_2)$.

Date de intrare

N
A[0][0] A[0][1] ... A[0][N-1]
A[1][0] A[1][1] ... A[1][N-1]
...
A[N-1][0] A[N-1][1] ... A[N-1][N-1]
(N linii și N coloane, '.' sau '#', fără spații)
Q
i1[0] j1[0] i2[0] j2[0]
i1[1] j1[1] i2[1] j2[1]
...
i1[Q-1] j1[Q-1] i2[Q-1] j2[Q-1]

Date de ieșire

ans[0]
ans[1]
...
ans[Q-1]

Restricții și precizări

• Se recomandă folosirea fastio.
• $1 \le N \le 690$
• $1 \le Q \le 100\ 000$
• $0 \le i_1, j_1, i_2, j_2 \lt N$
• Dacă nu există soluție, se va afișa -1.
• Cel mult $1\%$ (rotunjit în sus) din toate celulele sunt ocupate (cu excepția exemplului).
• Testele sunt generate random.

Exemplu

stdin

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

stdout

7
4
-1
6
4

Explicație

Pentru prima întrebare, distanța de la celula $(3, 0)$ la celula $(3, 3)$ este $7$. Un drum posibil este următorul: $(3, 0)$, $(3, 1)$, $(2, 1)$, $(1, 1)$, $(1, 2)$, $(1, 3)$, $(2, 3)$, $(3, 3)$.

#...#
#***.
#*#*.
1*#2.
..#..