暗闇の中で夜の蝶を導く必要があります。蝶の出発点は、時計回りに $0$ から $5$ まで番号が付けられた6本の放射状の経路の共通の中心です。経路 $0$ が主経路で、残りの5本は補助経路です。

経路のうち、特定の区間だけが照らされています。主経路には照らされた区間の集合が1つあり、5本すべての補助経路は別の1つの集合を共有しています。照らされた区間はすべて閉区間で、その端点は中心からの距離を表します。

各飛行の前に、正の実数の速度 $d$ を選ぶことができ、この速度は飛行中ずっと一定です。蝶は時刻 $0$ に中心から出発します。すべての正の整数時刻 $t$ に、蝶は経路 $(t \bmod 6)$ 上の、中心から距離 $t \cdot d$ の位置にいます。したがって、経路 $1,2,3,4,5,0,1,2,\ldots$ をこの順に訪れます。

$q$ 個のクエリが与えられ、それぞれ目標距離 $T$ を指定します。ある時刻 $k$ に、蝶を主経路上の中心から距離 $T$ の位置に到達させたいと考えています。したがって、$k$ は $6$ の正の倍数であり、$k \cdot d = T$ でなければなりません。すべての整数時刻 $1,2,\ldots,k$ に、蝶はその時点の経路上の照らされた区間内にいなければなりません。そうでなければ、暗闇に入って道に迷ってしまいます。時刻 $0$ を含む、それ以外の時刻には制約はありません。

各クエリについて、蝶が安全に目標に到達できる最も早い時刻 $k$ を求めてください。不可能な場合は -1 を出力してください。各クエリは独立で、クエリごとに $d$ を別々に選ぶことができます。

入力

最初の行に2つの整数 $n,m$ ($1 \le n,m \le 50$) が与えられます。これらはそれぞれ、主経路上の照らされた区間の個数と、5本すべての補助経路が共有する集合に含まれる照らされた区間の個数を表します。

続く $n$ 行のそれぞれに2つの整数 $l,r$ ($1 \le l \le r \le 10^{18}$) が与えられ、主経路上の照らされた区間 $[l,r]$ を表します。

続く $m$ 行のそれぞれに2つの整数 $l,r$ ($1 \le l \le r \le 10^{18}$) が与えられ、5本すべての補助経路が共有する照らされた区間 $[l,r]$ を表します。

各集合の中で、区間は互いに交わらず、左端点の昇順で与えられます。特に、連続する区間は $l_{i+1} > r_i$ を満たします。

次の行にクエリの個数を表す整数 $q$ ($1 \le q \le 100$) が与えられます。

続く $q$ 行のそれぞれに整数 $T$ ($1 \le T \le 10^{18}$) が与えられ、1つのクエリの目標距離を表します。

出力

各クエリについて、蝶が安全に目標に到達できる最も早い時刻 $k$ を1行に出力してください。不可能な場合は -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$ に目標に到達できます。最初の5つの整数時刻での距離は $1,2,3,4,5$ で、すべて補助経路上の照らされた区間 $[1,5]$ に含まれます。6番目の整数時刻では距離は $6$ で、主経路上の照らされた区間 $[6,6]$ に含まれます。

$T=12$ の場合、$d=1$ を選ぶと、蝶は時刻 $k=12$ に目標に到達できます。補助経路上にいるときの距離はすべて $[1,5] \cup [7,11]$ に含まれ、主経路上にいるときの距離は $6$ と $12$ です。時刻 $k=6$ に到達するには $d=2$ が必要ですが、その場合は時刻 $3$ に、補助経路上の中心から距離 $6$ の安全でない位置にいることになります。

下の図はクエリ $T=12$ を示しています。最初の2つの図は $d=1$、3つ目の図は $d=2$ の場合です。金色の線分と点は照らされた区間です。濃い青色の点にはその時刻が記されており、赤い十字は暗闇の中の位置を示しています。2つ目の図は時刻 $6$ の白抜きの点から続いています。破線の矢印は整数時刻での位置の順序だけを示しており、その間の実際の飛行経路を示すものではありません。

$T=18$ の場合、目標は主経路上のどの照らされた区間にも含まれないため、安全に到達することはできません。