대학생인 JOI는 버스를 타고 대학교에 통학합니다. JOI의 집과 그가 다니는 대학교는 모두 IOI 시 안에 있습니다. IOI 시에는 1부터 $N$까지 번호가 매겨진 $N$개의 버스 정류장이 있습니다. JOI의 집에서 가장 가까운 버스 정류장은 버스 정류장 1이고, 대학교에서 가장 가까운 버스 정류장은 버스 정류장 $N$입니다.

IOI 시에는 $M$대의 버스가 운행됩니다. 각 버스는 하루에 한 번, 정해진 버스 정류장에서 정해진 시각에 출발하여 정해진 버스 정류장에 정해진 시각에 도착합니다. 날짜를 넘겨서 운행하는 버스는 없습니다. JOI는 지정된 정류장 외의 장소에서는 버스에 타거나 내릴 수 없습니다.

매일 JOI는 한 대 이상의 버스를 타고 대학교에 통학합니다. JOI가 버스 간에 환승하는 데 걸리는 시간은 무시할 수 있다고 가정합니다. 즉, 어떤 버스 정류장에서 어떤 시각에 출발하는 버스로 환승하려면, 그 버스의 출발 시각 또는 그 이전에 해당 버스 정류장에 도착해 있기만 하면 됩니다. 또한 같은 버스 정류장을 여러 번 이용할 수도 있습니다.

이러한 조건에서 JOI는 수업 시간에 맞춰 대학교에 도착하려면 집에서 언제 출발해야 하는지 알고 싶어 합니다. 하지만 대학교에서 하루의 첫 수업이 시작하는 시각은 날마다 다릅니다. 주어진 $Q$일 동안, 그날 수업 시간에 맞추기 위해 버스 정류장 $N$에 몇 시까지 도착해야 하는지가 알려져 있습니다. 이 날들 각각에 대해, 수업 시간에 맞추려면 JOI는 늦어도 몇 시까지 버스 정류장 1에 도착해야 할까요?

과제

버스 운행에 대한 정보가 주어집니다. 또한 $Q$일 동안 버스 정류장 $N$에 도착해야 하는 시각이 주어집니다. 각 날에 대해 JOI가 버스 정류장 1에 도착해야 하는 가장 늦은 시각을 구하세요.

입력

표준 입력에서 다음 데이터를 읽으세요:

• 첫 번째 줄에는 공백으로 구분된 두 정수 $N$과 $M$이 주어지며, 이는 IOI 시에 $N$개의 버스 정류장과 $M$대의 버스가 있음을 나타냅니다.
• 다음 $M$개의 줄 중 $i$번째 줄($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 \neq B_i$)가 주어집니다. 이는 $i$번째 버스가 시각 $X_i$에 버스 정류장 $A_i$에서 출발하여 시각 $Y_i$에 버스 정류장 $B_i$에 도착함을 의미합니다. 단, 시각은 오전 0시 00분부터 경과한 시간을 밀리초 단위로 나타낸 것입니다.
• 다음 줄에는 버스 정류장 $N$의 도착 시각이 주어지는 날의 수를 나타내는 정수 $Q$가 주어집니다.
• 다음 $Q$개의 줄 중 $j$번째 줄($1 \le j \le Q$)에는 정수 $L_j$가 주어지며, 이는 $j$번째 날에 시각 $L_j$까지 버스 정류장 $N$에 도착해야 함을 나타냅니다.

출력

표준 출력으로 $Q$개의 줄을 출력하세요. $j$번째 줄($1 \le j \le Q$)에는 $j$번째 날에 JOI가 버스 정류장 1에 도착해야 하는 가장 늦은 시각을 나타내는 정수를 출력해야 합니다. 만약 수업 시간에 맞춰 대학교에 도착하는 것이 불가능하다면 -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

참고

시각 10까지 버스 정류장 5에 도착하는 것은 불가능합니다. 시각 30까지 도착하려면 시각 5에 4번째 버스를 타면 됩니다. 시각 60까지 도착하려면 다음과 같이 할 수 있습니다: 시각 10에 1번째 버스에 탑승합니다. 시각 25에 버스 정류장 2에 도착하여 1밀리초를 기다린 후 3번째 버스에 탑승합니다. 시각 50에 버스 정류장 5에 도착합니다. 시각 100까지 도착하려면 다음과 같이 할 수 있습니다: 시각 30에 5번째 버스에 탑승합니다. 시각 40에 버스 정류장 4에 도착하여 10밀리초를 기다린 후 6번째 버스에 탑승합니다. 시각 70에 버스 정류장 5에 도착합니다.

입력 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