Debes guiar a una mariposa nocturna a través de la oscuridad. Su punto de partida es el centro común de seis trayectorias radiales, numeradas en sentido horario de $0$ a $5$. La trayectoria $0$ es la trayectoria principal; las otras cinco son trayectorias auxiliares.

Solo ciertos intervalos de las trayectorias están iluminados. La trayectoria principal tiene un conjunto de intervalos iluminados, mientras que las cinco trayectorias auxiliares comparten otro conjunto. Todos los intervalos iluminados son cerrados, y sus extremos representan distancias desde el centro.

Antes de cada vuelo, puedes elegir una velocidad real positiva $d$, que permanece fija durante todo el vuelo. La mariposa parte del centro en el instante $0$. En cada instante entero positivo $t$, se encuentra en la trayectoria $(t \bmod 6)$ a una distancia $t \cdot d$ del centro. Por tanto, visita las trayectorias $1,2,3,4,5,0,1,2,\ldots$ en este orden.

Se te dan $q$ consultas, cada una de las cuales especifica una distancia objetivo $T$. Quieres que la mariposa llegue a la trayectoria principal en algún instante $k$, a una distancia $T$ del centro. Por tanto, $k$ debe ser un múltiplo positivo de $6$, y $k \cdot d = T$. En cada instante entero $1,2,\ldots,k$, la mariposa debe encontrarse dentro de un intervalo iluminado de su trayectoria actual; de lo contrario, caerá en la oscuridad y perderá el rumbo. No hay restricciones en los demás instantes, incluido el instante $0$.

Para cada consulta, encuentra el primer instante $k$ en el que la mariposa puede llegar a su objetivo de forma segura, o imprime -1 si no puede hacerlo. Las consultas son independientes, y puedes elegir $d$ por separado para cada consulta.

Entrada

La primera línea contiene dos enteros $n$ y $m$ ($1 \le n,m \le 50$), que representan, respectivamente, el número de intervalos iluminados de la trayectoria principal y del conjunto compartido por las cinco trayectorias auxiliares.

Cada una de las siguientes $n$ líneas contiene dos enteros $l$ y $r$ ($1 \le l \le r \le 10^{18}$), que representan un intervalo iluminado $[l,r]$ de la trayectoria principal.

Cada una de las siguientes $m$ líneas contiene dos enteros $l$ y $r$ ($1 \le l \le r \le 10^{18}$), que representan un intervalo iluminado $[l,r]$ compartido por las cinco trayectorias auxiliares.

Dentro de cada conjunto, los intervalos son disjuntos dos a dos y se dan en orden creciente de sus extremos izquierdos. En particular, los intervalos consecutivos satisfacen $l_{i+1} > r_i$.

La siguiente línea contiene un entero $q$ ($1 \le q \le 100$), que representa el número de consultas.

Cada una de las siguientes $q$ líneas contiene un entero $T$ ($1 \le T \le 10^{18}$), que representa la distancia objetivo de una consulta.

Salida

Para cada consulta, imprime en una línea independiente el primer instante $k$ en el que la mariposa puede llegar a su objetivo de forma segura, o -1 si no puede hacerlo.

Ejemplos

Entrada 1

2 2
6 6
12 12
1 5
7 11
3
6
12
18

Salida 1

6
12
-1

Nota

Para $T = 6$, elegir $d = 1$ permite que la mariposa llegue al objetivo en el instante $k = 6$. Las distancias en los primeros cinco instantes enteros son $1,2,3,4,5$, todas dentro del intervalo iluminado $[1,5]$ de las trayectorias auxiliares. En el sexto instante entero, la distancia es $6$, que está dentro del intervalo iluminado $[6,6]$ de la trayectoria principal.

Para $T = 12$, elegir $d = 1$ permite que la mariposa llegue al objetivo en el instante $k = 12$. Sus distancias mientras está en las trayectorias auxiliares están todas en $[1,5] \cup [7,11]$, mientras que sus distancias en la trayectoria principal son $6$ y $12$. Para llegar en el instante $k = 6$, necesitaría $d = 2$, pero entonces, en el instante $3$, estaría en una posición insegura a una distancia $6$ del centro en una trayectoria auxiliar.

Los diagramas de abajo muestran la consulta $T = 12$. Los dos primeros usan $d = 1$, y el tercero usa $d = 2$. Los segmentos y puntos dorados son intervalos iluminados. Los puntos azul oscuro están etiquetados con sus instantes, y la cruz roja marca una posición en la oscuridad. El segundo panel continúa desde el punto hueco del instante $6$. Las flechas discontinuas muestran solo el orden de las posiciones en instantes enteros, no la trayectoria real del vuelo entre ellas.

Para $T = 18$, el objetivo está fuera de todos los intervalos iluminados de la trayectoria principal, por lo que no se puede llegar a él de forma segura.