Find the Closest Available Rental Building

There are ( n ) buildings located along a straight road, numbered consecutively from ( 1 ) to ( n ) from west to east. The distance between any two adjacent buildings is ( 1 ) meter.

There are ( m ) disjoint intervals ( [l_i, r_i] ) representing segments of buildings that do not provide rental services. In addition, there is a school located in building number ( s ) (which is guaranteed to be in a no-rental zone).

Your task is to select a building ( p ) that provides rental service (i.e. it does not belong to any of the forbidden intervals) such that the distance to the school ( |s - p| ) is minimized. In case of a tie, choose the building with the smaller index.

You are given the values of ( n ), ( m ), and ( s ) in the first line, followed by ( m ) lines each containing two integers ( l_i ) and ( r_i ) (for ( 1 \leq i \leq m )). It is guaranteed that the intervals are disjoint and that building ( s ) is in one of the forbidden intervals.

inputFormat

The first line contains three integers ( n ), ( m ), and ( s ) ( (1 \leq s \leq n \leq 10^5,\ 0 \leq m \leq n) ). Each of the next ( m ) lines contains two integers ( l_i ) and ( r_i ) ( (1 \leq l_i \leq r_i \leq n) ), representing a segment where rental services are not provided.

outputFormat

Output a single integer representing the index of the building that provides rental service and minimizes the distance ( |s - p| ). In the case of a tie, output the smaller building index.

sample

10 2 5
3 5
7 8

6