Cerința

Se dă o hartă de NxN care conține spații libere (notate cu '.') și spații ocupate (notate cu '#'). Să se răspundă la Q interogări de forma i1 j1 i2 j2, unde se dorește să se afle distanța minimă de la celula (i1, j1) la celula (i2, j2).

Formatul input-ului

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]

Formatul output-ului

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

Restricții și precizări

• Se recomandă folosirea fastio
• 1 ≤ N ≤ 690
• 1 ≤ Q ≤ 100.000
• 0 ≤ i1, j1, i2, j2 < 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:

Intrare

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

Ieșire

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.
..#..