Маршрутки Оша
Утром студенты ОшГУ разъезжаются по городу на маршрутках. Остановки Оша пронумерованы от 1 до n; остановка 1 находится у главного корпуса университета, а остановка n — у подножия Сулайман-Тоо, где сегодня проходит студенческий квест.
Известно расписание на весь день: m рейсов. Рейс i отправляется с остановки a[i] в момент s[i] и без промежуточных остановок прибывает на остановку b[i] в момент f[i] (s[i] < f[i]). Время измеряется в секундах от начала суток.
Чтобы пересесть, нужно время: выйдя из маршрутки на остановке v в момент T, студент может сесть в любой рейс, отправляющийся с v в момент не раньше T + c[v] (переход к другой стороне улицы, поиск нужной маршрутки). На остановке 1 в начале пути пересадки нет: если студент пришёл туда в момент t, он может сесть в любой рейс с отправлением не раньше t. Ждать на остановках можно сколько угодно, ходить пешком между остановками нельзя.
Поступает q вопросов: Бакыт приходит на остановку 1 в момент t. В какой самый ранний момент он может оказаться на остановке n?
Входные данные
В первой строке — два целых числа n и m (2 ≤ n ≤ 200 000, 1 ≤ m ≤ 300 000).
Во второй строке — n целых чисел c[1], …, c[n] (0 ≤ c[v] ≤ 10⁹) — время пересадки на каждой остановке.
В каждой из следующих m строк — четыре целых числа a[i], b[i], s[i], f[i] (1 ≤ a[i], b[i] ≤ n, a[i] ≠ b[i], 0 ≤ s[i] < f[i] ≤ 10⁹).
Далее — число q (1 ≤ q ≤ 200 000) и q строк, в каждой одно целое число t (0 ≤ t ≤ 10⁹).
Выходные данные
Для каждого вопроса выведите в отдельной строке самый ранний момент прибытия на остановку n или -1, если в этот день добраться туда уже невозможно.
Пример 1
Вход:
4 6
0 5 2 0
1 2 0 10
1 3 5 12
2 4 14 20
3 4 13 30
2 4 16 18
1 4 25 40
4
0
5
6
26
Выход:
18
40
40
-1
Пояснение
Выйдя в момент 0, Бакыт едет рейсом 1 → 2 (прибытие в 10). На остановке 2 пересадка занимает 5 секунд, поэтому рейс в 14 он пропускает, а рейс в 16 успевает и прибывает в 18.
Выйдя в момент 5, он может уехать только рейсом 1 → 3 (прибытие в 12), но пересадка на остановке 3 занимает 2 секунды, и рейс в 13 уходит без него. Остаётся прямой рейс в 25 с прибытием в 40.
Система оценивания
| Подзадача | Баллы | Дополнительные ограничения |
|---|---|---|
| 1 | 20 | n, m, q ≤ 1000 |
| 2 | 25 | q ≤ 10 |
| 3 | 55 | без дополнительных ограничений |
Баллы за подзадачу начисляются, только если пройдены все её тесты.
Комментарии