Algolina と Bajtazar は Bajtowo に引っ越すことになり、新しい住居を探しています。Bajtowo には長い道路が一本あり、その道沿いに $n$ 個の建物が並んでいます。建物には $1$ から $n$ までの番号が付けられています。一部の建物は賃貸物件として提供されていますが、完全に居住者がいる建物もあります（そのような建物を「使用中」と呼びます）。

使用中の建物は、$m$ 個の互いに素な区間 $[l_i, r_i]$ によって記述できます。これは、建物番号 $x$ が $l_i \le x \le r_i$ を満たす場合、その建物 $x$ は使用中であることを意味します。

Algolina と Bajtazar は住居を選ぶ際に多くの要素を考慮しなければなりませんが、その一つに、息子の Bajtek が通う学校への近さがあります。この学校は建物番号 $s$ にあります（この建物は使用中であることが保証されています）。

Bajtek はまだ幼いため、両親は彼が学校まで遠くへ通うことを望んでいません。そのため、彼らは Bajtek の将来の学校にできるだけ近い空き建物を選びたいと考えています。隣り合う建物間の距離は常に一定であると仮定します。つまり、Bajtek の両親は $|s - p|$ が最小となるような建物番号 $p$ を見つけたいと考えています。

入力

最初の行には、3 つの整数 $n, m, s$ ($2 \le n \le 10^{12}, 1 \le m \le 1000, 1 \le s \le n$) が含まれており、それぞれ Bajtowo の建物の総数、使用中の建物の区間の数、Bajtek の将来の学校がある建物番号を表します。

続く $m$ 行には、使用中の建物の区間が記述されており、$i$ 番目の記述は 2 つの整数 $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$ が成り立ち、与えられた区間は互いに素であることが保証されます。さらに、Bajtowo には少なくとも一つの空き建物が存在することが保証されています。

出力

出力には、Algolina と Bajtazar が住むべき建物番号 $p$ を表す整数を 1 つ出力してください。この $p$ は $|s - p|$ を最小化するものです。そのような $p$ が複数存在する場合は、最も小さいものを出力してください。

入出力例

入力 1

10 2 7
5 9
1 2

出力 1

4

入力 2

15 4 9
4 5
10 13
1 1
6 9

出力 2

14

注記

最初の例では、建物番号 $p = 4$ と $p = 10$ が学校に最も近い空き建物です。したがって、答えは $p = 4$ となります。これは $|s - p|$ を最小化する複数の $p$ の中で、最も小さいものを選ぶ必要があるためです。

2 番目の例では、学校までの最小距離（5）を達成する唯一の空き建物は、建物番号 14 です。