열도

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

섬의 지도는 $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$이다. 단, 육지 칸에서 출발하여 육지 칸으로만 이동할 수 있으며, 한 번의 이동을 할 때 시작 칸과 도착 칸 사이에 바다 칸이 한 개라도 있다면 이동할 수 없다. 즉, 시작 칸과 도착 칸을 잇는 선분은 육지 칸으로만 이루어져 있어야 한다.

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

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

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

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

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

• $1 \leq N \leq 1 \, 000$.
• $1 \leq M \leq 1 \, 000$.
• $0\le A_{}$ ().