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

Условие

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

В воинской части города Шатров решили провести строевую подготовку по новым правилам. Сначала все солдаты выстраиваются в шеренгу по росту, начиная с самого низкого. Затем они выполняют команды вида: "С a по b — развернись!". Выполнение такой команды происходит следующим образом. Пусть a_pos — номер места в строю, на котором стоит a-й по росту солдат, а b_pos — b-й. Тогда отрезок строя с позиции min(a_pos, b_pos) до позиции max(a_pos, b_pos) должен развернуться. То есть, например, a-й по росту солдат поменяется местами с b-м.

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

• b_i < a_j
• b_j < a_i
• a_i < a_j, b_j < b_i
• a_j < a_i, b_i < b_j

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

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

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

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

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

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

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

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

4 2
1 4
2 3

4 2 3 1