버스 Batch Compilation commands

KOI 대학교에 다니는 상수는 버스를 타고 통학합니다. 상수의 집과 대학교는 모두 서울시내에 있습니다. 서울시에는 $N$개의 버스 정류장이 있으며 각각 $1$ 이상 $N$ 이하의 자연수 번호가 붙어 있습니다. 상수의 집은 $1$번 정류장 바로 앞에 있으며, KOI 대학교는 $N$번 정류장 바로 앞에 있습니다. 버스 정류장은 멀리 떨어져 있기 때문에 그 사이를 걸어다닐 수는 없습니다.

서울시에는 $M$대의 버스가 다니며 각 버스는 하루에 한 번 정해진 시각에 정해진 버스 정류장에서 출발하여 정해진 버스 정류장에 도착합니다. 1000만명이나 되는 서울 시민을 수용하기 위해 서울시의 버스들에게 휴일이란 없습니다. 상수는 일단 버스에 타면 이 버스가 목적지에 도착할 때까지 절대로 내릴 수 없습니다.

상수는 매일 1개 이상의 버스를 갈아타며 대학에 다닙니다. 상수는 날렵하기 때문에 버스를 갈아타거나, 집에서 1번 버스 정류장으로 가거나, $N$번 버스 정류장에서 강의실로 들어가는 데에 시간이 걸리지 않는다고 가정해도 좋습니다. 즉 상수가 시각 $t$에 출발하는 버스를 타기 위해서는 $t$ 이전 또는 $t$에 해당 버스 정류장에 서 있으면 됩니다. 또한 같은 버스 정류장을 여러 번 방문해도 됩니다.

상수는 이러한 조건을 만족하며 등교하여 수업 시작 시각에 맞추어 도착하기 위해 집에서 출발할 수 있는 가장 늦은 시각이 언제인지를 알고자 합니다. 아시다시피 상수는 대학생이기 때문에 매일 수업을 시작하는 시각이 다를 수 있습니다. 따라서 상수는 자신이 등교하는 $Q$일 각각에 대해 집에서 출발해야 할 가장 늦은 시각을 알고자 합니다. 상수가 언제 1번 정류장에 도착해야 수업 시간에 맞춰 $N$번 정류장에 도착할 수 있을까요?

해야 할 일

버스 운행 정보가 주어집니다. 또한 상수가 등교하는 $Q$일 각각의 수업 시작 시각이 주어집니다. (이 때까지는 $N$번 정류장에 도착해 있어야 합니다) 이 때 각 등교일마다 상수가 1번 정류장에 도착해야 할 가장 늦은 시각이 언제일지 구하는 프로그램을 작성하세요.

입력 형식

표준 입력으로 아래 입력을 받으세요.

• 첫 번째 줄에 두 개의 정수 서울시내 버스 정류장의 수 $N$과 버스의 수 $M$이 공백을 사이로 두고 주어집니다.
• $M$개 줄이 주어집니다. 이 중 $i$ ($1 \le i \le M$)번째 줄에는 4개의 정수 $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}$번 버스 정류장에 도착한다는 것을 의미합니다. 시각은 정오로부터의 경과 시간을 ms (1/1000초) 단위로 나타낸 것입니다.
• 다음 줄에는 상수가 등교하는 날의 수 $Q$가 주어집니다.
• $Q$개 줄이 주어집니다. 이 중 $j$ ($1 \le j \le Q$)번째 줄에는 정수 $L_{j}$가 주어집니다. 이것은 $j$번째 날에는 $N$번 버스 정류장에 시각 $L_{j}$까지 도착해야 한다는 것을 의미합니다.

출력 형식

표준 출력에 $Q$개 줄을 출력합니다. 이 중 $j$번째 줄 ($1 \le j \le Q$)에는 $j$번째 날에 상수가 1번 버스 정류장에 도착해야 할 가장 늦은 시각을 출력합니다. 단 시각 $L_{j}$ 안에 $N$번 버스 정류장에 도착할 수 없을 시 $-1$을 출력합니다.

제약 조건

• $2 \le N \le 100 000$
• $1 \le M \le 300 000$
• $0 \le X_{i} < Y_{i} \le 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점]

추가적인 제약 조건이 없습니다.

예제 입출력

입력

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
5
10
30

시각 10까지 도착하는 것은 불가능합니다.

시각 30까지 도착하려면 시각 5에 4번 버스를 타면 됩니다.

시각 60까지 도착하려면 다음과 같이 하면 됩니다.

• 시각 10에 1번 버스 승차
• 시각 25에 2번 버스 정류장에 도착, 1ms 동안 3번 버스 승차
• 시각 50에 5번 버스 정류장에 도착

시각 100까지 도착하려면 다음과 같이 하면 됩니다.

• 시각 30에 5번 버스 승차
• 시각 40에 4번 버스 정류장에 도착, 10ms 동안 6번 버스 승차
• 시각 70에 5번 버스 정류장에 도착

입력

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

출력

0
0
0
1
1
2