Назад!

3000 мс · 256 МБ · всё или ничего

Солдаты стоят в ряд и пронумерованы от $1$ до $n$ . Приказ «рядовые с $l$ по $r$ — назад!» переставляет солдат, стоящих на местах с $l$ по $r$ , в конец ряда, сохраняя между собой прежний порядок.

Выведите порядок после всех приказов.

Формат ввода

В первой строке — числа $n$ и $m$ ( $2 \le n \le 10^5$ , $1 \le m \le 10^5$ ). Далее $m$ приказов $l_i$ , $r_i$ .

Формат вывода

Выведите $n$ чисел — итоговый порядок.

Примеры

ввод

6 2
2 4
1 2

вывод

6 2 3 4 1 5

ввод

2 1
1 2

вывод

1 2

Разбор идеи от автора задачи. Сначала попробуйте сами.

Войдите, чтобы отправлять решения.