어둠 속에서 밤나비를 안내해야 합니다. 출발점은 시계 방향으로 $0$부터 $5$까지 번호가 붙은 여섯 개의 방사형 경로가 공유하는 중심입니다. 경로 $0$은 주 경로이고, 나머지 다섯 개는 보조 경로입니다.

경로의 특정 구간에만 불이 켜져 있습니다. 주 경로에는 하나의 불이 켜진 구간 집합이 있고, 다섯 보조 경로는 모두 또 다른 집합을 공유합니다. 불이 켜진 모든 구간은 닫힌 구간이며, 끝점은 중심으로부터의 거리를 나타냅니다.

각 비행 전에 양의 실수 속도 $d$를 선택할 수 있으며, 이 속도는 비행 내내 일정하게 유지됩니다. 나비는 시각 $0$에 중심에서 출발합니다. 모든 양의 정수 시각 $t$에 나비는 경로 $(t \bmod 6)$ 위에서 중심으로부터 $t \cdot d$만큼 떨어진 곳에 있습니다. 따라서 경로 $1,2,3,4,5,0,1,2,\ldots$를 이 순서대로 방문합니다.

목표 거리 $T$를 지정하는 질의가 $q$개 주어집니다. 나비가 어떤 시각 $k$에 주 경로 위에서 중심으로부터 거리 $T$에 도달하도록 하고 싶습니다. 따라서 $k$는 $6$의 양의 배수여야 하고, $k \cdot d = T$여야 합니다. 모든 정수 시각 $1,2,\ldots,k$에 나비는 현재 경로의 불이 켜진 구간 안에 있어야 합니다. 그렇지 않으면 어둠에 빠져 길을 잃습니다. 시각 $0$을 포함한 다른 시각에는 제한이 없습니다.

각 질의에 대해 나비가 목표에 안전하게 도달할 수 있는 가장 이른 시각 $k$를 구하거나, 불가능하면 $-1$을 출력하세요. 질의는 서로 독립적이며, 각 질의에 대해 $d$를 별도로 선택할 수 있습니다.

입력

첫 번째 줄에는 두 정수 $n$과 $m$ ($1 \le n,m \le 50$)이 주어집니다. 각각 주 경로의 불이 켜진 구간의 개수와 다섯 보조 경로가 모두 공유하는 집합의 구간 개수를 나타냅니다.

다음 $n$개의 줄에는 각각 두 정수 $l$과 $r$ ($1 \le l \le r \le 10^{18}$)이 주어지며, 주 경로의 불이 켜진 구간 $[l,r]$을 나타냅니다.

다음 $m$개의 줄에는 각각 두 정수 $l$과 $r$ ($1 \le l \le r \le 10^{18}$)이 주어지며, 다섯 보조 경로가 모두 공유하는 불이 켜진 구간 $[l,r]$을 나타냅니다.

각 집합 안에서 구간들은 서로 겹치지 않으며 왼쪽 끝점의 오름차순으로 주어집니다. 특히, 연속한 구간들은 $l_{i+1} > r_i$를 만족합니다.

다음 줄에는 질의의 개수를 나타내는 정수 $q$ ($1 \le q \le 100$)가 주어집니다.

다음 $q$개의 줄에는 각각 한 질의의 목표 거리를 나타내는 정수 $T$ ($1 \le T \le 10^{18}$)가 주어집니다.

출력

각 질의에 대해 나비가 목표에 안전하게 도달할 수 있는 가장 이른 시각 $k$를 별도의 줄에 출력하세요. 불가능하면 $-1$을 출력하세요.

예제

입력 1

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

출력 1

6
12
-1

참고

$T=6$일 때 $d=1$을 선택하면 나비는 시각 $k=6$에 목표에 도달합니다. 처음 다섯 정수 시각에서의 거리는 $1,2,3,4,5$로, 모두 보조 경로의 불이 켜진 구간 $[1,5]$ 안에 있습니다. 여섯 번째 정수 시각에서의 거리는 $6$이며, 이는 주 경로의 불이 켜진 구간 $[6,6]$ 안에 있습니다.

$T=12$일 때 $d=1$을 선택하면 나비는 시각 $k=12$에 목표에 도달합니다. 보조 경로 위에 있을 때의 거리는 모두 $[1,5] \cup [7,11]$ 안에 있고, 주 경로 위에 있을 때의 거리는 $6$과 $12$입니다. 시각 $k=6$에 도달하려면 $d=2$가 필요하지만, 그러면 시각 $3$에 보조 경로 위에서 중심으로부터 거리 $6$인 안전하지 않은 위치에 있게 됩니다.

아래 그림은 질의 $T=12$를 보여 줍니다. 처음 두 그림은 $d=1$을 사용하고, 세 번째 그림은 $d=2$를 사용합니다. 금색 선분과 점은 불이 켜진 구간입니다. 짙은 파란색 점에는 시각이 표시되어 있으며, 빨간색 십자 표시는 어둠 속의 위치를 나타냅니다. 두 번째 그림은 시각 $6$의 속이 빈 점에서 이어집니다. 점선 화살표는 정수 시각에서의 위치 순서만 나타내며, 그 사이의 실제 비행 경로를 나타내지는 않습니다.

$T=18$일 때 목표는 주 경로의 불이 켜진 모든 구간 밖에 있으므로 안전하게 도달할 수 없습니다.