Альголина и Байтазар переезжают в Байтово и ищут себе новое жилье. В Байтове есть только одна длинная дорога, вдоль которой стоит $n$ зданий. Пронумеруем их числами от $1$ до $n$. Некоторые из них предлагают квартиры в аренду, но часть из них полностью заселена (о таких зданиях мы будем говорить, что они заняты).

Занятые здания можно описать с помощью $m$ непересекающихся интервалов номеров $[l_i, r_i]$. Это означает, что если номер здания $x$ удовлетворяет условию $l_i \le x \le r_i$, то здание с номером $x$ занято.

Альголина и Байтазар должны учесть множество факторов при выборе жилья, и одним из них является близость к школе, в которую будет ходить их сын Байтек. Эта школа находится в здании с номером $s$ (гарантируется, что это здание занято).

Байтек еще маленький, и родители не хотят, чтобы ему приходилось слишком далеко добираться до школы. По этой причине они хотят выбрать свободное здание, которое находится как можно ближе к будущей школе Байтека. Мы предполагаем, что расстояния между соседними зданиями всегда одинаковы. Это означает, что родители Байтека хотят найти номер здания $p$ такой, что $|s - p|$ минимально.

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

В первой строке находятся три целых числа $n$, $m$ и $s$ ($2 \le n \le 10^{12}$, $1 \le m \le 1000$, $1 \le s \le n$), обозначающие соответственно: количество зданий в Байтове, количество интервалов номеров занятых зданий и номер здания, в котором находится будущая школа Байтека.

В следующих $m$ строках находятся описания очередных интервалов номеров занятых зданий, где $i$-е из этих описаний состоит из двух целых чисел $l_i, r_i$ ($1 \le l_i \le r_i \le n$). Для каждой пары $i, j$ ($1 \le i < j \le m$) выполняется $r_i < l_j$ или $r_j < l_i$, что означает, что данные интервалы не пересекаются. Дополнительно гарантируется, что в Байтове существует хотя бы одно свободное здание.

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

Выведите одно целое число $p$, обозначающее номер здания, в котором должны поселиться Альголина и Байтазар, чтобы минимизировать $|s - p|$. Если существует несколько таких чисел $p$, следует вывести наименьшее из них.

Примеры

Пример 1

10 2 7
5 9
1 2

4

Пример 2

15 4 9
4 5
10 13
1 1
6 9

14

Примечание

В первом примере здания с номерами $p = 4$ и $p = 10$ являются ближайшими к школе свободными зданиями. Таким образом, ответ — $p = 4$, так как из множества значений $p$, минимизирующих $|s - p|$, мы должны выбрать наименьшее.

Во втором примере единственным свободным зданием, достигающим минимального расстояния до школы (равного $5$), является здание с номером $14$.