Задача №2791. В начало строя!
Капрал Питуца любит командовать своим отрядом. Его любимый приказ «в начало строя». Он выстраивает свой отряд в шеренгу и оглашает последовательность приказов. Каждая приказ имеет вид «Солдаты с \(l_i\) по \(r_i\) — в начало строя!»
Пронумеруем солдат в начальном положении с 1 до \(n\), слева направо. Приказ «Солдаты с \(l_i\) по \(r_i\) — в начало строя!» означает, что солдаты, стоящие с \(l_i\) по \(r_i\) включительно, перемещаются в начало строя, сохраняя относительный порядок.
Например, если в некоторый момент солдаты стоят в порядке \(2, 3, 6, 1, 5, 4\), после приказа: «Солдаты с \(2\) по \(4\) — в начало строя!» порядок будет \(3, 6, 1, 2, 5, 4\).
По данной последовательности приказов найти конечный порядок солдат в строю.
В первой строке два целых числа \(n\) and \(m\) (\(2 \le n \le 100\,000\), \(1 \le m \le 100\,000\)) — количество солдат и количество приказов. Следующие \(m\) строк содержат по два целых числа \(l_i\) и \(r_i\) (\(1 \le l_i \le r_i \le n\)).
Выведите \(n\) целых чисел — порядок солдат в конечном положении после выполнения всех приказов.
6 3 2 4 3 5 2 2
1 4 5 2 3 6