Bus

JOI Spring Training Camp 2013/14
Original Statement / Submission Site

Problem Statement

JOI-kun is a university student who commutes to university by bus. Both his home and his university are located in IOI City.

There are N bus stops in IOI City, numbered from 1 to N. The bus stop nearest to JOI-kun's home is bus stop 1, and the bus stop nearest to his university is bus stop N.

There are M buses operating in IOI City. Each bus runs exactly once per day: it departs from a specified bus stop at a specified time and arrives at another specified bus stop at a specified time. No bus operates across midnight. JOI-kun cannot board or leave a bus at an intermediate stop.

Every day, JOI-kun travels to university using one or more buses. The time required to transfer between buses can be ignored. In other words, to board a bus departing from a bus stop at a certain time, it is sufficient that JOI-kun arrives at that bus stop at or before the bus's departure time. He may also use the same bus stop more than once.

Under these conditions, JOI-kun wants to know how late he may leave home and still arrive at university in time for class. The starting time of the first class differs from day to day.

For each of Q days, the latest time by which he must arrive at bus stop N is given. For each day, determine the latest time by which he must arrive at bus stop 1 in order to reach university in time.

Task

Given information about the bus services and, for each of Q days, the deadline for arriving at bus stop N, determine the latest time by which JOI-kun must arrive at bus stop 1 on each day.

Input

The input is given from standard input in the following format:

N M
A1 B1 X1 Y1
A2 B2 X2 Y2
...
AM BM XM YM
Q
L1
L2
...
LQ

• The first line contains two integers N and M, representing the number of bus stops and the number of buses.
• Each of the next M lines contains four integers Ai, Bi, Xi, and Yi. The i-th bus departs from bus stop Ai at time Xi and arrives at bus stop Bi at time Yi.
• Times are expressed in milliseconds elapsed since exactly midnight.
• The next line contains the integer Q.
• Each of the following Q lines contains an integer Lj, the latest time by which JOI-kun must arrive at bus stop N on the j-th day.

Output

Print Q lines.

On the j-th line, print the latest time by which JOI-kun must arrive at bus stop 1 on the j-th day. If it is impossible to reach bus stop N by time Lj, print -1.

Constraints

• 2 ≤ N ≤ 100000
• 1 ≤ M ≤ 300000
• 1 ≤ Ai, Bi ≤ N
• Ai ≠ Bi
• 0 ≤ Xi < Yi < 86400000
• 1 ≤ Q ≤ 100000
• 0 ≤ Lj < 86400000

Subtasks

Subtask 1 [20 points]

• N ≤ 2000
• M ≤ 2000
• Q = 1

Subtask 2 [15 points]

• N ≤ 2000
• M ≤ 2000

Subtask 3 [15 points]

• Q = 1

Subtask 4 [50 points]

There are no additional constraints.

Sample Input 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

Sample Output 1

-1
5
10
30

Explanation of Sample 1

It is impossible to arrive at bus stop 5 by time 10.

To arrive by time 30, JOI-kun can board the fourth bus at time 5.

To arrive by time 60, he can proceed as follows:

• Board the first bus at time 10.
• Arrive at bus stop 2 at time 25, wait for 1 millisecond, and board the third bus.
• Arrive at bus stop 5 at time 50.

To arrive by time 100, he can proceed as follows:

• Board the fifth bus at time 30.
• Arrive at bus stop 4 at time 40, wait for 10 milliseconds, and board the sixth bus.
• Arrive at bus stop 5 at time 70.

Sample Input 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

Sample Output 2

0
0
0
1
1
2