题目背景

PA 2025 R2C.

题目描述

有 $n$ 栋建筑在一条笔直的马路上，自西向东依次编号为 $1\sim n$。相邻两栋建筑的距离为 $1$ 米。

有 $m$ 个两两不交的区间 $[l_i,r_i]$，表示编号在 $[l_i,r_i]$ 内的房子不提供租赁服务。

有一所学校，在编号为 $s$ 的建筑中。保证编号为 $s$ 的建筑不提供租赁服务。

现在想要选择一栋提供租赁服务的建筑 $p$，最小化到学校的距离（即最小化 $|s-p|$）。请帮忙求出这栋建筑的编号。

输入格式

第一行，三个正整数 $n,m,s$。

接下来 $m$ 行，每行两个正整数 $l_i,r_i$。

数据保证：

• 编号为 $s$ 的建筑不提供租赁服务；
• $m$ 个区间两两不交；
• 至少存在一栋建筑提供租赁服务。

输出格式

输出一个正整数，表示选择建筑的编号。

特别地，若有多解，输出最小的那个编号。

10 2 7
5 9
1 2

4

15 4 9
4 5
10 13
1 1
6 9

14

提示

样例解释

• 样例 $1$ 解释：$p=4,10$ 是两个解。由于要求编号最小，输出 $4$。
• 样例 $2$ 解释：只有唯一的一栋提供租赁服务的建筑，即编号 $14$ 的建筑。

数据范围

• $2 \leq n \leq 10^{12}$；
• $1 \leq m \leq 1000$；
• $1 \leq s \leq n$；
• 编号为 $s$ 的建筑不提供租赁服务；
• $m$ 个区间两两不交；
• 至少存在一栋建筑提供租赁服务。