Студент JOI ездит в университет на автобусе. И его дом, и университет находятся в городе IOI. В городе $N$ автобусных остановок, пронумерованных от $1$ до $N$. Ближайшая к дому JOI остановка имеет номер $1$, а ближайшая к университету — номер $N$.

В городе IOI курсируют $M$ автобусов. Каждый из них один раз в день отправляется с заданной остановки в заданное время и прибывает на заданную остановку в заданное время. Ни одна поездка не пересекает границу между днями. JOI не может сесть в автобус или выйти из него посреди поездки.

Каждый день JOI добирается в университет на одном или нескольких автобусах с пересадками. Временем, необходимым на пересадку, можно пренебречь. Иными словами, чтобы пересесть на автобус, отправляющийся с некоторой остановки в некоторый момент, достаточно прибыть на эту остановку не позднее момента его отправления. Одну и ту же остановку можно посещать несколько раз.

При этих условиях JOI хочет знать, когда ему следует выйти из дома, чтобы успеть в университет к занятиям. Время начала первого занятия зависит от дня. Для каждого из $Q$ дней известно, к какому моменту нужно прибыть на остановку $N$, чтобы успеть к занятиям. Каков для каждого дня самый поздний момент, к которому JOI должен прибыть на остановку $1$, чтобы успеть?

Задание

Дана информация о движении автобусов. Также для каждого из $Q$ дней дан крайний срок прибытия на остановку $N$. Для каждого дня найдите самый поздний момент, к которому JOI должен прибыть на остановку $1$.

Входные данные

Считайте следующие данные со стандартного ввода.

• В первой строке записаны два целых числа $N$, $M$, разделённые пробелом. В городе IOI имеется $N$ остановок и курсирует $M$ автобусов.
• В $i$-й из следующих $M$ строк ($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$. Время задаётся в миллисекундах, прошедших с полуночи.
• В следующей строке записано целое число $Q$ — число дней, для которых задан крайний срок прибытия на остановку $N$.
• В $j$-й из следующих $Q$ строк ($1\le j\le Q$) записано целое число $L_j$. В день $j$ необходимо прибыть на остановку $N$ не позднее момента $L_j$.

Выходные данные

Выведите $Q$ строк в стандартный вывод. В $j$-й строке ($1\le j\le Q$) выведите целое число — самый поздний момент, к которому JOI должен прибыть на остановку $1$ в день $j$. Если успеть в университет к занятиям невозможно, выведите -1.

Ограничения

Все входные данные удовлетворяют следующим условиям.

• $2\le N\le 100\,000$.
• $1\le M\le 300\,000$.
• $0\le X_i<Y_i<86\,400\,000\ (=24\times60\times60\times1000)$ ($1\le i\le M$).
• $1\le Q\le 100\,000$.
• $0\le L_j<86\,400\,000\ (=24\times60\times60\times1000)$ ($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

Примечание

Прибыть на остановку $5$ не позднее момента $10$ невозможно.

Чтобы прибыть не позднее момента $30$, можно сесть на четвёртый автобус в момент $5$.

Чтобы прибыть не позднее момента $60$, можно действовать следующим образом.

• Сесть на первый автобус в момент $10$.
• Прибыть на остановку $2$ в момент $25$, подождать 1 миллисекунду и сесть на третий автобус.
• Прибыть на остановку $5$ в момент $50$.

Чтобы прибыть не позднее момента $100$, можно действовать следующим образом.

• Сесть на пятый автобус в момент $30$.
• Прибыть на остановку $4$ в момент $40$, подождать 10 миллисекунд и сесть на шестой автобус.
• Прибыть на остановку $5$ в момент $70$.

Входные данные 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