Elevator Simulation

You are given an elevator's starting floor and a sequence of n requests. Each request is a pair of integers \( (a, b) \) representing the starting floor and the destination floor respectively. Your task is to simulate the elevator's movement and output the sequence of floors at which it stops.

The simulation works as follows:

• Begin at the starting floor \( S \).
• For each request \( (a, b) \):
  • If the elevator's current floor is not \( a \), the elevator first moves to \( a \) and stops.
  • Then, the elevator moves to \( b \) and stops.

If there are no requests, simply output the starting floor.

The process can be defined by the recurrence: \[ \begin{aligned} &s_0 = S, \\ &\text{for } i \ge 1:\quad \text{if } s_{last} \neq a_i \text{ then append } a_i, \\ &\quad\quad append\ b_i. \end{aligned} \]

inputFormat

The input is given via standard input (stdin) in the following format:

S n
a1 b1
... 
 an bn

Where:

• S is the elevator's starting floor (an integer).
• n is the number of requests.
• Each of the next n lines contains two integers a and b representing the starting and destination floors of a request.

outputFormat

Output the final sequence of stops of the elevator on a single line, with each floor separated by a space.

## sample

1 3
0 5
3 8
8 2

1 0 5 3 8 2