Задача 1E. Суперсекретная информация ≡

Условие

Сотруднику одной компании, занимающейся секретными разработками, потребовалось доставить некоторый набор документов из одного офиса компании a в другой офис b. Так как информация в этих документах очень важная и не должна попасть в руки злоумышленников или конкурентов, для их перевозки можно использовать только охраняемый корпоративный транспорт - специальные шаттлы.

Возможно, что для того, чтобы добраться в другой офис, сотруднику придется сделать несколько пересадок. Кроме того, шаттлы ходят редко и строго в определенное время, а сотруднику необходимо попасть в другой офис как можно быстрее.

Необходимо написать программу, которая выведет минимальное время, которое потребуется сотруднику для того, чтобы добраться из офиса a в офис b.

Формат входных данных

Сначала вводится число N - общее число офисов компании (1 ≤ N ≤ 100), затем в новой строке - номера офисов a и b (1 ≤ a, b ≤ N). Далее следует число рейсов корпоративных шаттлов R (0 ≤ R ≤ 10⁵). После идут описания рейсов шаттлов: каждый рейс задается номером офиса отправления, временем отправления, номером офиса назначения и временем прибытия (все времена - целые от 0 до 10000). Если в момент t сотрудник приезжает в какой-то офис, то уехать из него он может в любой момент времени, начиная с t.

Формат выходных данных

Выведите минимальное время, через которое сотрудник сможет оказаться в офисе b. Если он не сможет добраться из офиса a в офис b с помощью указанных рейсов шаттлов, выведите −1.

Примеры тестов

3
1 3
4
1 0 2 5
1 1 2 3
2 3 3 5
1 1 3 10

5