Problem Description

There are $n$ train stations in a straight line, numbered from $1$ to $n$. There are $m$ railway tracks in total, and each track covers an interval of stations $[l_i, r_i]$.

At a station covered by multiple tracks, when a train passes through, it may switch tracks there. However, the train cannot turn around, and can only run in one direction (that is, it can only keep moving toward station $1$ or keep moving toward station $n$).

Person A starts from station $x$, meaning they board any train that passes through $x$ (this train may also depart from station $x$). This train may run on any track that covers station $x$, and its direction may be toward $1$ or toward $n$. After boarding, Person A falls asleep, and only wakes up when the train stops at the terminal station of some track. Ask which stations Person A may finally reach.

Note: The train must travel through at least one station. Also, after switching tracks, the train will not stop immediately; instead, it will continue moving along the current track.

Input Format

The first line contains three positive integers $n, m, x$, representing the number of stations, the number of tracks, and Person A’s starting station.

The next $m$ lines each contain two positive integers $l_i, r_i$, representing the operating interval of a track.

Output Format

Output one line containing several positive integers separated by single spaces, representing the stations that Person A may finally reach. Output them in increasing order of station number.

7 5 4
3 4
4 6
1 3
5 7
4 6

1 3 6 7

Hint

Sample 1 Explanation

Starting from station $4$, if the train takes the first track, it can reach the terminal station $3$, or it can then continue along the third track to reach the terminal station $1$.

Starting from station $4$, if the train takes the second track, it can reach the terminal station $6$, or it can switch to the fourth track at station $5$ and reach the terminal station $7$.

So the final output in order is $1, 3, 6, 7$.

Constraints

For all testdata, it is guaranteed that $1 \le n, m \le 2 \times 10^5$, $1 \le x \le n$, $1 \le l_i < r_i \le n$.

Special Property A: It is guaranteed that $x = 1$.

Translated by ChatGPT 5