Algolina and Bajtazar are moving to Bajtowo and are looking for a new place to live. In Bajtowo, there is only one long road with $n$ buildings along it. Let us number them from $1$ to $n$. Some of them offer apartments for rent, but some are fully occupied (we will refer to such buildings as occupied).

We can describe the occupied buildings using $m$ disjoint intervals of numbers $[l_i, r_i]$. This means that if a building number $x$ satisfies $l_i \le x \le r_i$, then the building with number $x$ is occupied.

Algolina and Bajtazar must consider many factors when choosing their home, and one of them is the proximity to the school that their son, Bajtek, will attend. This school is located in the building with number $s$ (we guarantee that this building is occupied).

Bajtek is still small, and his parents do not want him to have to travel too far to school. For this reason, they want to choose a free building that is as close as possible to Bajtek's future school. We assume that the distances between consecutive buildings are always the same. This means that Bajtek's parents want to find a building with number $p$ such that $|s - p|$ is as small as possible.

Input

The first line contains three integers $n$, $m$, and $s$ ($2 \le n \le 10^{12}$, $1 \le m \le 1000$, $1 \le s \le n$), representing, respectively: the number of buildings in Bajtowo, the number of intervals of occupied buildings, and the number of the building where Bajtek's future school is located.

The next $m$ lines contain descriptions of the consecutive intervals of occupied buildings, where the $i$-th description consists of two integers $l_i, r_i$ ($1 \le l_i \le r_i \le n$). For every pair $i, j$ ($1 \le i < j \le m$), either $r_i < l_j$ or $r_j < l_i$ holds, which means that the given intervals are disjoint. Additionally, we guarantee that there exists at least one free building in Bajtowo.

Output

The output should contain a single integer $p$ representing the building number where Algolina and Bajtazar should live to minimize $|s - p|$. If there are multiple such numbers $p$, you must output the smallest one.

Examples

Input 1

10 2 7
5 9
1 2

Output 1

4

Input 2

15 4 9
4 5
10 13
1 1
6 9

Output 2

14

Note

In the first example, buildings with numbers $p = 4$ and $p = 10$ are the free buildings closest to the school. Therefore, the answer is $p = 4$, because among the many values of $p$ that minimize $|s - p|$, we must choose the smallest one.

In the second example, the only free building that achieves the minimum distance to the school (equal to $5$) is the building with number $14$.