Задача B. Держать строй! ≡

Условие

При подготовке пакета были использованы материалы сайта школьных олимпиад по информатике.

В воинской части города Шатров решили провести строевую подготовку по новым правилам. Сначала все солдаты выстраиваются в шеренгу по росту, начиная с самого низкого. Затем они выполняют команды вида: "С $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$) выполняется ровно одно из следующих условий:

• $b_i \lt a_j$
• $b_j \lt a_i$
• $a_i \lt a_j$, $b_j \lt b_i$
• $a_j \lt a_i$, $b_i \lt b_j$

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

Первая группа тестов проверяется в момент сдачи задачи на проверку и стоит 40 баллов. Баллы за эту группу начисляются только при прохождении всех тестов группы. Для всех тестов этой группы выполнено условие $n \le 1000$ и $m \le 1000$.

Вторая группа тестов проверяется после окончания олимпиады и стоит 60 баллов. Баллы за тесты этой группы начисляются пропорционально количеству пройденных тестов.

Формат входного файла

В первой строке входного файла дано количество солдат $n$ ($1 \le n \le 100000$) и количество команд $m$ ($1 \le m \le n/2$). В следующих $m$ строках даны сами команды. Каждая команда описана двумя числами $a_i$ и $b_i$ ($1 \le a_i \lt b_i \le n$).

Формат выходного файла

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

Примеры тестов

4 2
1 4
2 3

4 2 3 1