Train Station Reachability

You are given n train stations arranged in a straight line and numbered from \(1\) to \(n\). There are m train tracks; each track covers a continuous segment of stations represented by an interval \([l_i, r_i]\). For any station that is covered by multiple tracks, a train passing through that station may switch from one track to another, but a train cannot change its running direction. In other words, once a train begins moving in one fixed direction (either toward station \(1\) or toward station \(n\)), it continues in that direction.

Little A starts at station \(x\) by boarding any train that passes through \(x\) (this train may even originate from \(x\)). The train he boards may be running on any track that covers station \(x\) and might be going either toward \(1\) or \(n\). Once he boards, he falls asleep and only wakes up when the train reaches the endpoint (terminal station) of the track on which it is running. However, note that the train must travel at least one station before stopping, and when switching tracks the train does not stop immediately but continues along the newly chosen track.

Your task is to determine the final station that Little A can optimally reach. In other words, among all possible choices (including taking a train in the upward direction and one in the downward direction), output the terminal station that is farthest away from \(x\). More formally, let the upward travel (toward \(n\)) yield a terminal station \(U\) (where \(U > x\)) and the downward travel (toward \(1\)) yield a terminal station \(D\) (where \(D < x\)). If both directions are possible, choose the one for which \(|U - x| \ge |x - D|\). If only one valid move exists, output its terminal station. If no move is possible (i.e. no track allows the train to travel at least one station), output \(x\) itself.

Note: When switching tracks, a valid track switch from the current train is only allowed if the station at which the switch occurs is strictly interior to the track’s interval (so that the train travels at least one station on the new track).

The intervals may be used in an iterative manner. For upward direction, starting from \(x\), if there exists an interval \([l, r]\) with \(l \le x < r\) then the train can reach \(r\). Then, from that station, if there is an interval \([l, r]\) with \(l \le current\_station < r\), the train can extend its journey further, and so on. A similar process applies for downward direction.

inputFormat

The first line contains three integers (n), (m) and (x) ((1 \le x \le n)). Each of the next (m) lines contains two integers (l_i) and (r_i) ((1 \le l_i \le r_i \le n)), representing a track covering stations from (l_i) to (r_i).

outputFormat

Output a single integer — the terminal station that Little A can reach by choosing the optimal train (i.e. the one which, among the valid upward and downward journeys, has the larger absolute distance from (x)).

sample

10 3 5
3 7
6 10
1 4

10