JOI 君 הוא סטודנט שנוסע לאוניברסיטה באוטובוס. ביתו והאוניברסיטה שלו נמצאים בעיר IOI. בעיר יש $N$ תחנות אוטובוס, הממוספרות מ־$1$ עד $N$. התחנה הקרובה לביתו היא תחנה $1$, והתחנה הקרובה לאוניברסיטה היא תחנה $N$.

בעיר פועלות $M$ נסיעות אוטובוס. כל אוטובוס יוצא פעם אחת ביום מתחנה קבועה בזמן קבוע, ומגיע לתחנה קבועה בזמן קבוע. אף נסיעה אינה נמשכת מעבר לחצות. JOI 君 אינו יכול לעלות לאוטובוס או לרדת ממנו באמצע הנסיעה.

בכל יום JOI 君 מגיע לאוניברסיטה באמצעות נסיעה באוטובוס אחד או יותר. ניתן להזניח את הזמן הנדרש להחלפת אוטובוס. כלומר, כדי לעלות לאוטובוס שיוצא מתחנה בזמן מסוים, די להגיע לתחנה בזמן היציאה או לפניו. מותר להשתמש באותה תחנה יותר מפעם אחת.

בתנאים אלה, JOI 君 רוצה לדעת מתי עליו לצאת מהבית כדי להגיע בזמן לשיעור. שעת תחילת השיעור הראשון משתנה מיום ליום. עבור $Q$ ימים נתונה השעה המאוחרת ביותר שבה עליו להגיע לתחנה $N$ כדי להספיק לשיעור. עבור כל יום, מהי השעה המאוחרת ביותר שבה הוא יכול להגיע לתחנה $1$ ועדיין להספיק?

משימה

נתונים פרטי נסיעות האוטובוסים, וכן מועדי ההגעה הנדרשים לתחנה $N$ עבור $Q$ ימים. עבור כל מועד, מצאו את השעה המאוחרת ביותר שבה JOI 君 יכול להגיע לתחנה $1$.

קלט

קראו את הנתונים הבאים מהקלט הסטנדרטי.

• השורה הראשונה מכילה שני מספרים שלמים $N,M$, המופרדים ברווח. הם מציינים שבעיר IOI יש $N$ תחנות ו־$M$ נסיעות אוטובוס.
• השורה ה־$i$ מבין $M$ השורות הבאות ($1\le i\le M$) מכילה ארבעה מספרים שלמים $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$.
• השורה ה־$j$ מבין $Q$ השורות הבאות ($1\le j\le Q$) מכילה מספר שלם $L_j$. ביום ה־$j$ יש להגיע לתחנה $N$ לכל המאוחר בזמן $L_j$.

פלט

הדפיסו $Q$ שורות לפלט הסטנדרטי. בשורה ה־$j$ ($1\le j\le Q$), הדפיסו מספר שלם המציין את השעה המאוחרת ביותר שבה JOI 君 יכול להגיע לתחנה $1$ ביום ה־$j$. אם אי אפשר להגיע לאוניברסיטה בזמן לשיעור, הדפיסו -1.

מגבלות

כל נתוני הקלט מקיימים את התנאים הבאים.

• $2\le N\le100\,000$.
• $1\le M\le300\,000$.
• $0\le X_i<Y_i<86\,400\,000=24\times60\times60\times1000$ ($1\le i\le M$).
• $1\le Q\le100\,000$.
• $0\le L_j<86\,400\,000=24\times60\times60\times1000$ ($1\le j\le Q$).

תתי־משימות

תת־משימה 1 [20 נקודות]

מתקיימים התנאים הבאים.

• $N\le2\,000$.
• $M\le2\,000$.
• $Q=1$.

תת־משימה 2 [15 נקודות]

מתקיימים התנאים הבאים.

• $N\le2\,000$.
• $M\le2\,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$.

כדי להגיע עד הזמן $60$, אפשר לפעול כך:

• לעלות לאוטובוס הראשון בזמן $10$.
• להגיע לתחנה $2$ בזמן $25$, להמתין אלפית שנייה אחת ולעלות לאוטובוס השלישי.
• להגיע לתחנה $5$ בזמן $50$.

כדי להגיע עד הזמן $100$, אפשר לפעול כך:

• לעלות לאוטובוס החמישי בזמן $30$.
• להגיע לתחנה $4$ בזמן $40$, להמתין 10 אלפיות שנייה ולעלות לאוטובוס השישי.
• להגיע לתחנה $5$ בזמן $70$.

קלט 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