D. A number game

**单点时限: **2.0 sec

**内存限制: **256 MB

Foxity and Foxitu are good friends. They like to play number games. One day, Foxity played ICPC with his teammates, leaving Foxitu alone at labs. So he played a number game with himself.

There are $n$ numbers from $1$ to $n$ in a set, each time he can choose two distinct number $a$ and $b$($a \ne b$). He firstly remove $ a $ and $ b $ from this set, then insert $a+b$ and $ \lvert a-b \rvert $ to the set. His goal is to leave the set with only two elements, and He can only operate on this set at most $ n $ times.

Please provide any of his possible operation sequence.

There will be no identical elements in the set, and identical elements are treated as one element.

One line contains one integer $ n(2 \le n \le 10^5) $ ,which is the size of the set.

The first line contains an integer $m$, which is the number of operations.

Follow $m$ lines with two integer $a$ and $b$, which represents each operation.

Input

10

Output

5 4 5 1 9 3 7 2 8 4 6

Input

6

Output

3 1 6 2 5 3 4

We guarantee that the first $9$ test data satisfying that $n$ is less than $11$.

通知

比赛状态发生变化，点 OK 刷新。

通知