Між населеними пунктами відбуваються пасажирські рейси на машинах часу.

На момент часу 0 ви знаходитесь в пункті \(𝐴\) . Вам дано розклад рейсів. Потрібно опинитися в пункті \(B\) якомога раніше (тобто найменший можливий момент часу).

При цьому дозволяється робити пересадки з одного рейсу на інший. Якщо ви прибуваєте до певного пункту в момент часу \(𝑇\) , то ви можете виїхати з нього будь-яким рейсом, який відправляється з цього пункту в момент часу \(𝑇\) або пізніше (але не раніше).

Формат вхідних даних

У першому рядку вводиться число \(𝑁\) – кількість населених пунктів ( \(1≤ N≤ 1000\)).

Другий рядок містить два числа \(𝐴\) та \(𝐵\) – номери початкового та кінцевого пунктів.

У третьому рядку задається \(𝐾\) – кількість рейсів (\(0≤ K≤1000\)).

Наступні \(𝐾\) рядків містять опис рейсів, по одному на рядку. Кожен опис є четвіркою цілих чисел. Перше число кожної четвірки задає номер пункту відправлення, друге – час відправлення, третє – пункт призначення, четверте – час прибуття. Номери пунктів – натуральні числа з діапазону від 1 до \(𝑁\). Пункт призначення та пункт відправлення можуть збігатися. Час вимірюється в деяких абсолютних одиницях і визначається цілим числом, по модулю не перевищує \(10^9\) . Оскільки рейси здійснюються на машинах часу, то час прибуття може бути як більшим за час відправлення, так і меншим, або рівним йому. Гарантується, що вхідні дані такі, що дістатися з пункту \(𝐴\) до пункту \(𝐵\) завжди можна.

Формат вихідних даних

Виведіть мінімальний час, коли ви зможете опинитися в пункті \(𝐵 \).

Приклад вхідних даних

2
1 1
2
1 1 2 10
1 10 1 9

Приклад вихідних даних

0

Приклад вхідних даних

1
1 1
3
1 3 1 -5
1 -5 1 -3
1 -4 1 -10

Приклад вихідних даних

-10

Приклад вхідних даних

5
1 2
6
1 0 3 10
4 2 2 -10
4 14 2 -7
3 10 2 10
2 0 4 2
3 10 4 12

Приклад вихідних даних

-10