JOI, a university student, commutes to university by bus. Both JOI's home and the university he attends are located within IOI City. There are $N$ bus stops in IOI City, numbered from 1 to $N$. The bus stop nearest to JOI's home is bus stop 1, and the bus stop nearest to the university is bus stop $N$.

There are $M$ buses running in IOI City. Each bus departs from a designated bus stop at a scheduled time and arrives at a designated bus stop at a scheduled time, once per day. There are no buses that operate across different days. JOI cannot board or alight from a bus at any point other than the designated stops.

Every day, JOI commutes to the university by taking one or more buses. Assume that the time it takes for JOI to transfer between buses is negligible. That is, to transfer to a bus that departs from a certain bus stop at a certain time, he only needs to have arrived at that bus stop at or before that bus's departure time. Also, he may use the same bus stop multiple times.

Under these conditions, JOI wants to know when he should leave his home to arrive at the university in time for his classes. However, the time the first class of the day starts at the university varies from day to day. For $Q$ given days, it is known by what time he must arrive at bus stop $N$ to be in time for class that day. For each of these days, by what time at the latest must JOI arrive at bus stop 1 to be in time for class?

Task

You are given information about the bus operations. Furthermore, for $Q$ days, you are given the time by which he must arrive at bus stop $N$. For each day, find the latest time by which JOI must arrive at bus stop 1.

Input

Read the following from standard input:

• The first line contains two integers $N$ and $M$, separated by a space, representing that there are $N$ bus stops and $M$ buses in IOI City.
• The $i$-th line of the following $M$ lines ($1 \le i \le M$) contains four integers $A_i, B_i, X_i, Y_i$ ($1 \le A_i \le N, 1 \le B_i \le N, A_i \neq B_i$), separated by spaces. This means the $i$-th bus departs from bus stop $A_i$ at time $X_i$ and arrives at bus stop $B_i$ at time $Y_i$. Note that the time is represented as the elapsed time in milliseconds from 0:00 AM.
• The next line contains an integer $Q$, representing the number of days for which the arrival time at bus stop $N$ is given.
• The $j$-th line of the following $Q$ lines ($1 \le j \le Q$) contains an integer $L_j$, indicating that on the $j$-th day, he must arrive at bus stop $N$ by time $L_j$.

Output

Output $Q$ lines to standard output. The $j$-th line ($1 \le j \le Q$) should contain an integer representing the latest time by which JOI must arrive at bus stop 1 on the $j$-th day. If it is impossible to arrive at the university in time for class, output -1.

Constraints

All input data satisfy the following conditions:

• $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$).

Subtasks

Subtask 1 [20 points]

The following conditions are satisfied: $N \le 2\,000$. $M \le 2\,000$. * $Q = 1$.

Subtask 2 [15 points]

The following conditions are satisfied: $N \le 2\,000$. $M \le 2\,000$.

Subtask 3 [15 points]

• $Q = 1$ is satisfied.

Subtask 4 [50 points]

There are no additional constraints.

Examples

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

Output 1

-1
5
10
30

Note

It is impossible to arrive at bus stop 5 by time 10. To arrive by time 30, one can take the 4th bus at time 5. To arrive by time 60, one can do the following: Board the 1st bus at time 10. Arrive at bus stop 2 at time 25, wait 1 millisecond, and board the 3rd bus. Arrive at bus stop 5 at time 50. To arrive by time 100, one can do the following: Board the 5th bus at time 30. Arrive at bus stop 4 at time 40, wait 10 milliseconds, and board the 6th bus. Arrive at bus stop 5 at time 70.

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

Output 2

0
0
0
1
1
2