삼각형 모험

포닉스는 $N \times M$ 크기의 격자에서 살고 있었다. 각 칸은 정사각형이며, 포닉스는 상하좌우로 인접한 칸으로 자유롭게 이동할 수 있었다.

어느 날 사악한 마법사가 각 칸에 넘을 수 없는 대각선 모양의 벽을 설치했다. 그 결과 각 칸은 직각이등변삼각형 모양의 두 영역으로 나뉘었다. 포닉스는 상하좌우로는 이전처럼 이동할 수 있지만, 대각선 벽을 넘을 수는 없다. 즉, 대각선이 아닌 변을 통해 인접한 삼각형으로만 이동할 수 있다. 포닉스는 자주 다니던 $Q$개의 경로에 대해 새로운 최소 이동 횟수를 계산하려 한다. $Q$개의 질문은 다음과 같이 주어진다.

• $x\_1 \ y\_1 \ t\_1 \ x\_2 \ y\_2 \ t\_2$: $(x\_1, y\_1, t\_1)$에서 출발해 $(x\_2, y\_2, t\_2)$로 도착하기 위한 이동 횟수의 최솟값을 구하여라.

첫 번째 줄에 격자의 크기를 나타내는 정수 $N$, $M$과 질문의 개수 $Q$가 공백으로 구분되어 주어진다. ($1 \leq N, M \leq 500; 1 \leq Q \leq 300\ 000$)

두 번째 줄부터 $N$개의 줄에 걸쳐 길이 $M$의 문자열이 주어진다. $i$번째 줄의 $j$번째 문자는 $i$번째 행 $j$번째 열 칸에 나타난 대각선 벽의 형태를 의미한다. Z는 우상향 대각선, N은 우하향 대각선을 의미한다.

$N+2$번째 줄부터 $Q$개의 줄에 걸쳐 $x\_1 \ y\_1 \ t\_1 \ x\_2 \ y\_2 \ t\_2$ 형태의 질문이 주어진다. ($1 \leq x\_1, x\_2 \leq N; 1 \leq y\_1, y\_2 \leq M; 0 \leq t\_1, t\_2 \leq 1$)

주어지는 수는 모두 정수이다. $t = 0$은 해당 좌표의 위쪽 삼각형 영역을, $t = 1$은 아래쪽 삼각형 영역을 의미한다.

각 질문에 대해 $(x\_1, y\_1, t\_1)$에서 출발해 $(x\_2, y\_2, t\_2)$로 도착하기 위한 이동 횟수의 최솟값을 한 줄에 하나씩 순서대로 출력한다. 해당하는 경로가 존재하지 않으면 -1을 출력한다.

포닉스의 모험기는 후대에도 포스테키안들에게 전설로 전해진다. 포스텍은 이를 기억하기 위해 학생회관 한편에 모험 당시의 격자를 재현해 두었다.