Debido a la dificultad de los problemas, algunos participantes deciden escapar de esta competición. Sin embargo, para evitarlo, los MALVADOS autores de los problemas han construido un laberinto en la salida del estadio. El laberinto consiste en una cuadrícula de $n \times m$, en la que se encuentran la entrada, la salida y $k$ agujeros negros. Los participantes que pisen accidentalmente un agujero negro caerán en él y nunca podrán escapar de la competición.

Para empeorar las cosas, los autores de los problemas también pueden cambiar las coordenadas de la entrada y de la salida. Tú, un pobre participante que comienza en la entrada y desea llegar a la salida sin pisar ningún agujero negro, solo puedes moverte a una de las cuatro casillas adyacentes en cada paso. Quieres saber, después de cada cambio de las coordenadas de la entrada y de la salida, cuál es el número mínimo de pasos necesarios para llegar a la salida desde la entrada.

Entrada

La primera línea de la entrada contiene cuatro enteros $n, m, k, q$ ($1 \le n, m \le 200\,000$, $nm \le 200\,000$, $0 \le k \le 42$, $1 \le q \le 100\,000$), que indican, respectivamente, el número de filas, el número de columnas, el número de agujeros negros del laberinto y el número de consultas.

Las siguientes $k$ líneas contienen la descripción de los agujeros negros. Cada una contiene dos enteros $x, y$ ($1 \le x \le n$, $1 \le y \le m$), que indican las coordenadas de un agujero negro. No hay dos agujeros negros en la misma posición.

Las últimas $q$ líneas contienen la descripción de las consultas. Cada una de las $q$ líneas contiene cuatro enteros $x_s, y_s, x_t, y_t$ ($1 \le x_s, x_t \le n$, $1 \le y_s, y_t \le m$), donde $(x_s, y_s)$ son las coordenadas de la entrada y $(x_t, y_t)$ son las de la salida.

Salida

Para cada consulta, imprime un número en una línea que indique el número mínimo de pasos necesarios para llegar a la salida desde la entrada. Si es imposible llegar a la salida, imprime $-1$. Se debe considerar imposible cuando la entrada o la salida coincida con un agujero negro.

Ejemplos

Entrada 1

5 5 4 7
2 2
2 3
3 2
3 3
2 1 3 4
1 1 1 1
2 2 2 2
1 1 1 5
2 2 5 5
2 1 2 4
1 1 3 3

Salida 1

6
0
-1
4
-1
5
-1

Entrada 2

2 3 2 1
1 2
2 1
1 1 2 3

Salida 2

-1

Nota

A continuación se muestran los diagramas del laberinto y de la primera consulta del primer ejemplo.

(a) El laberinto. (b) Un posible camino más corto para la primera consulta. Leyenda: entrada, salida, agujero negro, un paso.

Figura 1: Diagramas de los datos de ejemplo.