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$ 的建筑。