Bus

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

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

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

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

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

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

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

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

• 2 ≤ N ≤ 100 000．
• 1 ≤ M ≤ 300 000．
• 0 ≤ Xi < Yi < 86 400 000 (= 24 × 60 × 60 × 1000) (1 ≤ i ≤ M)．
• 1 ≤ Q ≤ 100 000．
• 0 ≤ Lj < 86 400 000 (= 24 × 60 × 60 × 1000) (1 ≤ j ≤ Q)．