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 的父母想要找到一個編號為 $p$ 的建築物，使得 $|s - p|$ 最小化。

輸入格式

第一行包含三個整數 $n, m$ 和 $s$ ($2 \le n \le 10^{12}, 1 \le m \le 1000, 1 \le s \le n$)，分別代表 Bajtowo 的建築物總數、已佔用建築物的區間數量，以及 Bajtek 未來學校所在的建築物編號。

接下來的 $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$，這意味著給定的區間是不相交的。此外，我們保證 Bajtowo 中存在至少一棟空閒的建築物。

輸出格式

輸出一個整數 $p$，代表 Algolina 和 Bajtazar 應該居住的建築物編號，以最小化 $|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$ 值中，我們必須選擇最小的一個。

在第二個範例中，唯一達到與學校最小距離（等於 $5$）的空閒建築物是編號為 $14$ 的建築物。