大学生の JOI 君はバスで通学している．JOI 君の自宅も JOI 君の通う大学も IOI 市内にある．IOI 市には $N$ 個のバス停があり，$1$ から $N$ までの番号が付いている．JOI 君の自宅の最寄りはバス停 $1$ で，大学の最寄りはバス停 $N$ である．

IOI 市内を走るバスは $M$ 本あり，それぞれのバスは１日に１回，定められた時刻に定められたバス停を出発し，定められた時刻に定められたバス停に到着する．日付をまたぐような運行を行うバスは存在しない．JOI 君はバスに途中で乗ったりバスから途中で降りたりすることはできない．

JOI 君は毎日，１本以上のバスを乗り継いで大学に通っている．JOI 君がバスを乗り換えるのにかかる時間は無視できるとする．すなわちある時刻にあるバス停を出発するバスに乗り換えるためには，そのバスの出発時刻またはそれ以前にそのバス停に到着していればよい．また，同じバス停を複数回利用してもよい．

そのような条件のもとで，JOI 君はいつ家を出れば授業に間に合うように大学に到着できるかを知りたい．ただし大学は１日の初めの授業が開始する時刻が日によって異なる．ある $Q$ 日間について，その日の授業に間に合うためにはバス停 $N$ にいつまでに到着すればよいかがわかっている．それぞれの日について，JOI 君は遅くともいつまでにバス停 $1$ に到着すれば授業に間に合うだろうか．

課題

バスの運行に関する情報が与えられる．さらにある $Q$ 日間について，バス停 $N$ にいつまでに到着すればよいかが与えられるので，それぞれについて，JOI 君が遅くともいつまでにバス停 $1$ に到着すればよいかを求めよ．

入力

標準入力から以下の入力を読み込め．

• １行目には，２つの整数 $N,M$ が空白を区切りとして書かれており，IOI 市内には $N$ 個のバス停があり $M$ 本のバスが走っていることを表す．
• 続く $M$ 行のうちの $i$ 行目（$1 \le i \le M$）には，$4$ つの整数 $A_i,B_i,X_i,Y_i$（$1 \le A_i \le N$，$1 \le B_i \le N$，$A_i \ne B_i$）が空白を区切りとして書かれている．これは $i$ 番目のバスが，バス停 $A_i$ を時刻 $X_i$ に出発し，バス停 $B_i$ に時刻 $Y_i$ に到着することを表す．ただし時刻は午前０時ちょうどからの経過時間をミリ秒単位で表したものである．
• 次の行には整数 $Q$ が書かれている．これは，バス停 $N$ にいつまでに到着すればよいかが与えられる日数が $Q$ 日間であることを表す．
• 続く $Q$ 行のうちの $j$ 行目（$1 \le j \le Q$）には，整数 $L_j$ が書かれている．これは $j$ 番目の日にはバス停 $N$ に時刻 $L_j$ までに到着しなければならないことを示す．

出力

標準出力に $Q$ 行出力せよ．$j$ 行目（$1 \le j \le Q$）に，$j$ 番目の日に JOI 君が遅くともいつまでにバス停 $1$ に到着すればよいかを表す整数を出力せよ．ただし，授業に間に合うように大学に到着することが不可能なときは -1 を出力せよ．

制約

すべての入力データは以下の条件を満たす．

• $2 \le N \le 100\,000$．
• $1 \le M \le 300\,000$．
• $0 \le X_i < Y_i < 86\,400\,000$（$=24\times60\times60\times1000$）（$1 \le i \le M$）．
• $1 \le Q \le 100\,000$．
• $0 \le L_j < 86\,400\,000$（$=24\times60\times60\times1000$）（$1 \le j \le Q$）．

小課題

小課題 1 [20 点]

以下の条件を満たす．

• $N \le 2\,000$．
• $M \le 2\,000$．
• $Q=1$．

小課題 2 [15 点]

以下の条件を満たす．

• $N \le 2\,000$．
• $M \le 2\,000$．

小課題 3 [15 点]

• $Q=1$ を満たす．

小課題 4 [50 点]

追加の制限はない．

入出力例

入力 1

5 6
1 2 10 25
1 2 12 30
2 5 26 50
1 5 5 20
1 4 30 40
4 5 50 70
4
10
30
60
100

出力 1

-1
5
10
30

注記

バス停 $5$ に時刻 $10$ までに到着することはできない．

時刻 $30$ までに到着するためには，時刻 $5$ に $4$ 番目のバスに乗ればよい．

時刻 $60$ までに到着するためには次のようにすればよい．

• 時刻 $10$ に $1$ 番目のバスに乗車．
• 時刻 $25$ にバス停 $2$ に到着し，$1$ ミリ秒待って $3$ 番目のバスに乗車．
• 時刻 $50$ にバス停 $5$ に到着．

時刻 $100$ までに到着するためには次のようにすればよい．

• 時刻 $30$ に $5$ 番目のバスに乗車．
• 時刻 $40$ にバス停 $4$ に到着し，$10$ ミリ秒待って $6$ 番目のバスに乗車．
• 時刻 $70$ にバス停 $5$ に到着．

入力 2

3 8
1 2 1 5
1 3 0 1
1 3 2 8
2 3 2 3
2 3 3 4
2 3 4 5
2 3 5 6
2 3 6 7
6
3
4
5
6
7
8

出力 2

0
0
0
1
1
2