악랄한 문제 출제자

일부 참가자는 어려운 문제 때문에 이 대회에서 도망치기로 결정한다. 이를 막기 위해 악랄한 출제진은 경기장 출구에 미로를 만들어 두었다. 미로는 $n \times m$ 격자이며, 입구와 출구가 있고 $k$개의 블랙홀이 있다. 블랙홀에 실수로 빠진 참가자는 그 안으로 떨어져 대회에서 영원히 탈출할 수 없다.

더 나쁜 것은, 출제진이 입구와 출구의 좌표를 바꿀 수 있다는 점이다. 당신은 입구에서 출발해 블랙홀을 밟지 않고 출구에 도달하려는 가난한 참가자다. 한 번의 이동으로는 상하좌우로 인접한 칸 중 한 칸으로만 갈 수 있다. 출제진이 입구와 출구의 좌표를 바꿀 때마다, 입구에서 출구까지 가는 데 필요한 최소 이동 횟수를 구하라.

첫 줄에 네 정수 $n, m, k, q$ $(1 \leq n, m \leq 200\,000, nm \leq 200\,000, 0 \leq k \leq 42, 1 \leq q \leq 100\,000)$가 주어진다. 각각 격자의 행 수, 열 수, 블랙홀의 개수, 질의의 개수이다.

다음 $k$개의 줄에는 블랙홀의 좌표 $x, y$ $(1 \leq x \leq n, 1 \leq y \leq m)$가 한 줄에 두 정수로 주어진다. 같은 위치에 블랙홀이 두 개 있는 경우는 없다.

마지막 $q$개의 줄에는 질의가 주어진다. 각 줄에는 네 정수 $x_s, y_s, x_t, y_t$ $(1 \leq x_s, x_t \leq n, 1 \leq y_s, y_t \leq m)$가 주어지며, $(x_s, y_s)$는 입구, $(x_t, y_t)$는 출구의 좌표이다.

각 질의마다 입구에서 출구까지 도달하는 데 필요한 최소 이동 횟수를 한 줄에 하나씩 출력한다. 도달할 수 없으면 $-1$을 출력한다. 입구나 출구가 블랙홀과 같은 위치에 있으면 도달할 수 없는 것으로 본다.

미로의 모습과 첫 번째 질의에 대한 최단 경로 예시는 아래 그림과 같다.