JOI เป็นนักศึกษามหาวิทยาลัยที่เดินทางไปเรียนด้วยรถบัส ทั้งบ้านและมหาวิทยาลัยของเขาอยู่ในเมือง IOI เมือง IOI มีป้ายรถบัส $N$ ป้าย หมายเลข $1$ ถึง $N$ ป้ายที่ใกล้บ้านของ JOI ที่สุดคือป้าย $1$ และป้ายที่ใกล้มหาวิทยาลัยที่สุดคือป้าย $N$

มีรถบัส $M$ เที่ยวให้บริการในเมือง IOI รถบัสแต่ละเที่ยวออกจากป้ายที่กำหนดในเวลาที่กำหนด และถึงป้ายที่กำหนดในเวลาที่กำหนด วันละหนึ่งครั้ง ไม่มีรถบัสเที่ยวใดเดินทางข้ามวัน JOI ไม่สามารถขึ้นหรือลงรถบัสระหว่างทางได้

ทุกวัน JOI เดินทางไปมหาวิทยาลัยด้วยการโดยสารรถบัสหนึ่งเที่ยวขึ้นไป โดยถือว่าเวลาที่ใช้เปลี่ยนรถนั้นน้อยจนละเลยได้ กล่าวคือ หากจะเปลี่ยนไปขึ้นรถบัสที่ออกจากป้ายหนึ่งในเวลาหนึ่ง เขาเพียงต้องมาถึงป้ายนั้นก่อนหรือในเวลาออกเดินทางของรถบัส นอกจากนี้ เขาสามารถใช้ป้ายเดิมหลายครั้งได้

ภายใต้เงื่อนไขเหล่านี้ JOI ต้องการรู้ว่าควรออกจากบ้านเมื่อใดจึงจะไปถึงมหาวิทยาลัยทันเรียน แต่เวลาเริ่มชั้นเรียนแรกของแต่ละวันแตกต่างกัน สำหรับช่วงเวลา $Q$ วัน เขารู้แล้วว่าในแต่ละวันต้องถึงป้าย $N$ ไม่เกินเวลาใดจึงจะทันเรียน ในแต่ละวัน JOI ต้องถึงป้าย $1$ อย่างช้าที่สุดเมื่อใดจึงจะทันเรียน?

งานที่ต้องทำ

กำหนดข้อมูลการเดินรถบัส และเวลาที่ต้องไปถึงป้าย $N$ สำหรับแต่ละวันในช่วง $Q$ วัน จงหาเวลาช้าที่สุดที่ JOI ต้องไปถึงป้าย $1$ สำหรับแต่ละวัน

ข้อมูลนำเข้า

อ่านข้อมูลต่อไปนี้จากข้อมูลนำเข้ามาตรฐาน

• บรรทัดแรกมีจำนวนเต็มสองจำนวน $N,M$ คั่นด้วยช่องว่าง หมายความว่าเมือง IOI มีป้ายรถบัส $N$ ป้าย และรถบัส $M$ เที่ยว
• บรรทัดที่ $i$ ($1 \le i \le M$) ใน $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$ หมายความว่ามี $Q$ วันที่กำหนดเวลาที่ต้องไปถึงป้าย $N$
• บรรทัดที่ $j$ ($1 \le j \le Q$) ใน $Q$ บรรทัดถัดไปมีจำนวนเต็ม $L_j$ หมายความว่าในวันที่ $j$ ต้องถึงป้าย $N$ ไม่เกินเวลา $L_j$

ข้อมูลส่งออก

แสดงผล $Q$ บรรทัดทางข้อมูลส่งออกมาตรฐาน ในบรรทัดที่ $j$ ($1 \le j \le Q$) ให้แสดงจำนวนเต็มที่เป็นเวลาช้าที่สุดที่ JOI ต้องไปถึงป้าย $1$ ในวันที่ $j$ หากไม่สามารถไปถึงมหาวิทยาลัยทันเรียนได้ ให้แสดง -1

ข้อจำกัด

ข้อมูลนำเข้าทั้งหมดเป็นไปตามเงื่อนไขต่อไปนี้

• $2 \le N \le 100\,000$
• $1 \le M \le 300\,000$
• $0 \le X_i < Y_i < 86\,400\,000$ ($=24 \times 60 \times 60 \times 1000$) ($1 \le i \le M$)
• $1 \le Q \le 100\,000$
• $0 \le L_j < 86\,400\,000$ ($=24 \times 60 \times 60 \times 1000$) ($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$ สามารถขึ้นรถบัสเที่ยวที่ 4 เวลา $5$

หากต้องการถึงไม่เกินเวลา $60$ สามารถทำดังนี้

• ขึ้นรถบัสเที่ยวที่ 1 เวลา $10$
• ถึงป้าย $2$ เวลา $25$ รอ 1 มิลลิวินาที แล้วขึ้นรถบัสเที่ยวที่ 3
• ถึงป้าย $5$ เวลา $50$

หากต้องการถึงไม่เกินเวลา $100$ สามารถทำดังนี้

• ขึ้นรถบัสเที่ยวที่ 5 เวลา $30$
• ถึงป้าย $4$ เวลา $40$ รอ 10 มิลลิวินาที แล้วขึ้นรถบัสเที่ยวที่ 6
• ถึงป้าย $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