버스

대학생 JOI는 버스로 통학한다. JOI의 집과 JOI가 다니는 대학은 모두 IOI시에 있다. IOI시에는 $N$개의 버스 정류장이 있고 $1$부터 $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 \ne B_i$)가 공백을 구분으로 쓰여 있다. 이는 $i$번째 버스가 버스 정류장 $A_i$를 시각 $X_i$에 출발해 버스 정류장 $B_i$에 시각 $Y_i$에 도착한다는 것을 나타낸다. 시각은 오전 0시 정각부터 경과한 시간을 밀리초 단위로 나타낸 것이다.
• 다음 줄에는 정수 $Q$가 쓰여 있다. 이는 버스 정류장 $N$에 언제까지 도착해야 하는지가 주어지는 날이 $Q$일이라는 것을 나타낸다.
• 이어지는 $Q$줄 중 $j$번째 줄 ($1 \le j \le Q$)에는 정수 $L_j$가 쓰여 있다. 이는 $j$번째 날에는 버스 정류장 $N$에 시각 $L_j$까지 도착해야 한다는 것을 나타낸다.

표준 출력에 $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$).