열도

바다 한가운데에 설곽 열도가 있다. 설곽 열도는 여러 개의 작은 섬들로 이루어져 있다. 각 섬은 상하좌우로 인접한 육지 칸들로 이루어진 하나의 연결 영역이고, 모든 바다는 연결되어 있다. 단, 바다는 육지와 다르게 대각선으로 인접한 칸도 연결된 것으로 생각한다.

\begin {center} \begin{tabular}{cc} \includegraphics[height=5cm]{island_example1.png} & \end{tabular} \end {center}

섬의 지도는 $0$과 $1$로만 이루어진 $[0, N+1] \times [0, M+1]$ 격자 형태로 나타낼 수 있다. $i$번째 행, $j$번째 열에 위치한 칸을 $(i,j)$칸이라 할 때, 지도 상의 숫자 $A_{i, j}$에 대해 $A_{i, j} = 1$은 $(i,j)$칸이 육지임을 의미하며, $A_{i, j} = 0$은 $(i,j)$칸이 바다임을 의미한다. 이때, 육지 칸은 $[1, N] \times [1, M]$ 범위에만 존재할 수 있다.

설곽 열도에는 버스가 운행하고 있는데, 버스를 통해 같은 행의 임의의 칸 또는 같은 열의 임의의 칸으로 이동할 수 있다. 이때 발생하는 비용은 이동 횟수당 $1$이다. 단, 육지 칸에서 출발하여 육지 칸으로만 이동할 수 있으며, 한 번의 이동을 할 때 시작 칸과 도착 칸 사이에 바다 칸이 한 개라도 있다면 이동할 수 없다. 즉, 시작 칸과 도착 칸을 잇는 선분은 육지 칸으로만 이루어져 있어야 한다.

\begin {center} \end {center}

\textrm{SSHS} 여행사는 설곽 열도를 여행하려고 하는 관광객들을 위해, 설곽 열도의 임의의 두 육지 칸 사이를 버스를 타고 이동할 때 발생하는 비용의 최솟값을 계산해주는 서비스를 제공하려고 한다. \textrm{SSHS} 여행사를 도와 $Q$개 상황의 비용을 계산해주자.

첫 줄에 설곽 열도의 크기를 나타내는 정수 $N$과 $M$이 공백으로 구분되어 주어진다.

다음 $N$줄에 걸쳐 설곽 열도의 지도가 주어진다. 그중 $i$번째 줄은 $A_{i, 1}$, $A_{i, 2}$, $\cdots$, $A_{i, M}$이 공백으로 구분되어 주어진다. $[1, N] \times [1, M]$ 범위의 $A_{i, j}$만 주어짐에 유의하라.

다음 줄에 수행해야 하는 쿼리의 개수 $Q$가 주어진다.

다음 $Q$줄에 걸쳐 각 쿼리의 내용이 x y z w의 형식으로 주어진다. 이 쿼리는 설곽 열도의 $(x, y)$ 칸에서 $(z, w)$ 칸으로 버스를 타고 이동할 때 발생하는 최소 비용을 구하는 쿼리이다.

각각의 쿼리 {\tt x y z w}에 대하여 쿼리의 정답을 출력한다.

만약 버스로 $(x, y)$칸과 $(z, w)$ 칸 사이를 이동할 수 없다면 $-1$을 출력한다.

• $1 \leq N \leq 1 \, 000$.

• $1 \leq M \leq 1 \, 000$.

• $0 \leq A_{i, j} \leq 1$ ($1 \leq i \leq N, 1 \leq j \leq M$).

• $A_{i, 0} = A_{i, M+1} = 0$ ($0 \leq i \leq N+1$)

• $A_{0, j} = A_{N+1, j} = 0$ ($0 \leq j \leq M+1$)

• $1 \leq Q \leq 100 \, 000$.

• $1 \leq x_i \leq N$ ($1 \leq i \leq Q$).

• $1 \leq y_i \leq M$ ($1 \leq i \leq Q$).

• $1 \leq z_i \leq N$ ($1 \leq i \leq Q$).

• $1 \leq w_i \leq M$ ($1 \leq i \leq Q$).

• $A_{x_i, y_i} = 1$ ($1 \leq i \leq Q$).

• $A_{z_i, w_i} = 1$ ($1 \leq i \leq Q$).

• 서브태스크 1(21점): 모든 $i (1 \leq i \leq Q)$에 대해 $y_i = 1$이고, 모든 $i (1 \leq i \leq N)$에 대해 $A_{i,1}=1$이다.

• 서브태스크 2(34점): $A_{i,j}=A_{i+1,j}=A_{i,j+1}=A_{i+1,j+1}=1$ 인 $(i, j)$ 쌍은 존재하지 않는다.

• 서브태스크 3(45점): 추가 제한 조건이 없습니다.