29446번 - Держать строй! 다국어

В воинской части города Ковров решили провести строевую подготовку по новым правилам. Сначала все солдаты выстраиваются в шеренгу по росту, начиная с самого низкого. Затем они выполняют команды вида: <<С $a$ по $b$ - развернись!>>. Выполнение такой команды происходит следующим образом. Пусть $a_{pos}$ --- номер места в строю, на котором стоит $a$-ый по росту солдат, а $b_{pos}$ --- $b$-ый. Тогда отрезок строя с позиции $\min(a_{pos}, b_{pos})$ до позиции $\max(a_{pos}, b_{pos})$ должен развернуться. То есть, например, $a$-ый по росту солдат поменяется местами с $b$-ым.

Завтра утром молодой прапорщик Андрей Юрьевич будет проводить строевую подготовку в первый раз за свою службу, и на это придет посмотреть командир его части. Поэтому Андрей Юрьевич выписал вечером все команды на листочек и поручил Вам, как самому умному солдату, узнать до утра, как будет выглядеть шеренга после выполнения всех команд. Также известно, что для любых двух команд $i$ и $j$($i \ne j$) выполняется ровно одно из следующих условий:

1. $b_i < a_j$
2. $b_j < a_i$
3. $a_i < a_j$, $b_j < b_i$
4. $a_j < a_i$, $b_i < b_j$

То есть, любая пара отрезков, разворачиваемых по команде, или вложены друг в друга, или не пересекаются.

В первой строке входного файла дано количество солдат $n$ ($ 1 \le n \le 100,000$) и количество команд $m$ ($1 \le m \le \frac{n}{2}$). В следующих $m$ строках даны сами команды. Каждая команда описана двумя числами $a_i$ и $b_i$ ($1 \le a_i < b_i \le n$)

В единственной строке выведите через пробел $n$ чисел, где $i$ - число, равное номеру по росту солдата, стоящего на $i$-том месте.