Descripción

La compañía ferroviaria IOI está operando líneas en una vía férrea. En una línea recta hay ~N~ estaciones, numeradas de ~1~ a ~N~. Para cada ~i~ (~1 \le i \le N - 1~), la estación ~i~ y la estación ~i + 1~ están conectadas directamente por una vía férrea.

La compañía ferroviaria IOI opera ~M~ líneas, numeradas del ~1~ al ~M~. En la línea ~j~ (~1 \le j \le M~), la estación de comienzo es la estación ~A_j~, y la estación terminal es la estación ~B_j~. Un tren para en cada estación. Es decir, si ~A_j < B_j~ un tren de la línea ~j~ se detiene en la estación ~A_j~, estación ~A_j + 1, ...~ estación ~B_j~, en ese orden. Si ~A_j > B_j~, un tren de línea ~j~ se detiene en las estaciones ~A_j, A_j - 1, ...~ estación ~B_j~, en ese orden.

OCI-cub es un viajero. El tiene ~Q~ planes de viaje. En el k-ésimo plan (~1 \le k \le Q~), viaja de la estación ~S_k~ a la estación ~T_k~ por .

Sin embargo, OCI-cub está cansado de un largo viaje. Quiere coger un tren libre y conseguir un asiento. Así, OCI-cub decide tomar el tren de una línea en una estación sólo si ésta es la parada K-ésima o anterior a la estación de partida de la línea. En otras palabras, si ~A_j < B_j~, puede coger un tren de la línea ~j~ sólo en la estación ~A_j~, estación ~A_j + 1, ...~ estación min {~A_j + K - 1~, ~B_j - 1~}. Si ~A_j > B_j~, sólo podrá tomar un tren de la línea ~j~ en las estaciones ~A_j~, ~A_j - 1, ...~ estación max {~A_j - K + 1~, ~B_j + 1~}. OCI-cub se bajará del tren en una estación comprendida entre la estación próxima a la que toma el tren y la estación terminal, ambas inclusive.

En estas condiciones, OCI-cub quiere minimizar el número de veces que toma el tren.

Tarea

Dada la información de las líneas de la compañía ferroviaria IOI y los planes de viaje de OCI-cub, escribe un programa que calcule, para cada uno de los planes de OCI-cub, el número mínimo de tiempos de toma de trenes necesarios para que OCI-cub pueda conseguir.

Entrada

Lea los siguientes datos de la entrada estándar. Los valores dados son todos enteros.

~N K~

~M~

~A_1 B_1~

~A_2 B_2~

~.~

~.~

~A_M B_M~

~Q~

~S_1 T_1~

~S_2 T_2~

~.~

~.~

~S_Q T_Q~

Salida

Escriba ~Q~ líneas en la salida estándar. La línea k-ésima (~1 \le k \le Q~) debe contener el número mínimo de veces que se toman trenes necesarios para que JOI-cub logre el plan k-ésimo. Si no es posible alcanzar el plan k-ésimo, la salida será ~-1~.

Restricciones

• ~2 \le N \le 100 000~.
• ~1 \le K \le N - 1~.
• ~1 \le M \le 200 000~.
• ~1 \le A_j \le N (1 \le j \le M~).
• ~1 \le B_j~ = ~N~ (~1 \le j \le M~).
• ~A_j~ ≠ ~B_j~ (~1 \le j \le M~).
• (~A_j~, ~B_j~) ≠ (~A_k, B_k~) (~1 \le j < k \le M~).
• ~1 \le Q \le 50 000~.
• ~1 \le S_k \le N~ (~1 \le k \le Q~).
• ~1 \le T_k \le N~ (~1 \le k \le Q~).
• ~S_k~ ≠ ~T_k~ (~1 \le k \le Q~).
• (~S_k, T_k~) ≠ (~S_l, T_l~) (~1 \le k < l \le Q~).

Subtareas

1. (8 puntos) ~N \le 300~, ~M \le 300~, ~Q \le 300~.
2. (8 puntos) ~N \le 2 000~, ~M \le 2 000~, ~Q \le 2 000~.
3. (11 puntos) ~Q = 1~.
4. (25 puntos) ~K = N - 1~.
5. (35 puntos) ~A_j < B_j~ (~1 \le j \le M~), ~S_k < T_k~ (~1 \le k \le Q~).
6. (13 puntos) No hay restricciones adicionales.

Ejemplos de entrada y salida

Ejemplo de entrada #1

5 2
2
5 1
3 5
3
5 3
3 2
2 1

Ejemplo de salida #1

1
2
-1

En el primer plan, OCI-cub viaja de la Estación 5 a la Estación 3. Por ejemplo, este plan se logra si OCI-cub toma un tren de la Línea 1 en la Estación 5, y se baja del tren en la Estación 3. En total, OCI-cub tomará un tren.

Dado que es imposible lograr el plan tomando menos de un tren, la salida 1 en la primera línea.

En el segundo plan, OCI-cub viaja de la Estación 3 a la Estación 2. Por ejemplo, este plan se logra si OCI-cub toma un tren de la Línea 2 en la Estación 3, se baja del tren en la Estación 4, toma un tren de la Línea 1 en la Estación 4, y se baja del tren en la Estación 2. En total, OCI-cub tomará dos trenes. Como es imposible lograr el plan tomando menos de dos trenes, sale 2 en la segunda línea.

En el tercer plan, OCI-cub viaja de la Estación 2 a la Estación 1. Como es imposible para OCI-cub lograr este plan, la salida es -1 en la tercera línea.

Este ejemplo de entrada satisface las restricciones de las subtareas 1, 2, 6.

Ejemplo de entrada #2

6 3
2
1 6
5 1
4
5 1
6 3
3 6
2 1

Ejemplo de salida #2

1
-1
1
2

Este ejemplo de entrada satisface las restricciones de las subtareas 1, 2, 6.

Ejemplo de entrada #3

6 5
4
3 1
2 4
5 3
4 6
5
1 5
3 2
2 6
6 3
5 4

Ejemplo de salida #3

-1
1
2
-1
1

Este ejemplo de entrada satisface las restricciones de las subtareas 1, 2, 4 y 6.