题目描述

题目译自 PA 2025 Runda 2 Szkoła

Algolina 和 Bajtazar 要搬到字节镇，正在寻找新家。字节镇只有一条长街，沿街有 $n$ 栋建筑，编号从 $1$ 到 $n$。其中一些建筑提供出租公寓，但有些已被全部住满（我们称这些为已占用建筑）。

已占用建筑可以用 $m$ 个互不相交的编号区间 $\left[l_{i}, r_{i}\right]$ 描述。也就是说，如果建筑编号 $x$ 满足 $l_{i} \leq x \leq r_{i}$，则该建筑已占用。

他们在挑选新家时要考虑很多因素，其中一个是离儿子 Bajtek 未来学校的距离。学校位于编号为 $s$ 的建筑（保证此建筑已占用）。Bajtek 还小，父母不希望他上学路途太远，因此想找一栋离学校最近的空闲建筑。假设相邻建筑间距离相等，他们的目标是找到编号 $p$ 的建筑，使 $|s-p|$ 尽可能小。

输入格式

输入的第一行包含三个整数 $n, m, s$ $(2 \leq n \leq 10^{12}, 1 \leq m \leq 1000, 1 \leq s \leq n)$，分别表示字节镇的建筑总数、已占用建筑区间的数量，以及学校所在建筑的编号。

接下来的 $m$ 行描述已占用建筑的区间，每行包含两个整数 $l_{i}, r_{i}$ $(1 \leq l_{i} \leq r_{i} \leq n)$，表示第 $i$ 个区间。对于任意 $i, j$ $(1 \leq i < j \leq m)$，满足 $r_{i} < l_{j}$ 或 $r_{j} < l_{i}$，即所有区间互不相交。保证字节镇至少有一栋空闲建筑。

输出格式

输出一个整数 $p$，表示 Algolina 和 Bajtazar 应选择的建筑编号，使 $|s-p|$ 最小。若存在多个满足条件的 $p$，输出其中最小的编号。

10 2 7
5 9
1 2

4

学校在 $7$ 号建筑，已占用区间为 $[1,2]$ 和 $[5,9]$。空闲建筑 $4$ 和 $10$ 离学校最近（距离均为 $3$），因要求最小编号，输出 $4$。

15 4 9
4 5
10 13
1 1
6 9

14

学校在 $9$ 号建筑，已占用区间为 $[1,1]$、$[4,5]$、$[6,9]$、$[10,13]$。空闲建筑 $14$ 距离学校最近（距离为 $5$），故输出 $14$。