Astar

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

Pe prima linie se citește numărul $N$.

Pe următoarele $N$ linii, se citește matricea $A$, formată din caractere. Fiecare element al matricei poate fi fie . (punct), fie # (diez). Nu există spații între caracterele din fiecare linie.

După matrice, se citește un număr întreg $Q$, care reprezintă numărul de interogări.

Pe următoarele $Q$ linii, fiecare linie conține câte patru numere întregi $i_1$, $j_1$, $i_2$ și $j_2$.

Date de ieșire

Pentru fiecare dintre cele $Q$ interogări, se afișează pe o linie separată rezultatul corespunzător.

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