Description

You need to implement a data structure (you can refer to the title) to maintain an ordered sequence.

It must support the following operation: reverse a segment. For example, if the original ordered sequence is $5\ 4\ 3\ 2\ 1$, and the reversed segment is $[2, 4]$, then the result is $5\ 2\ 3\ 4\ 1$.

Input Format

The first line contains two positive integers $n, m$, denoting the length of the sequence and the number of operations. Initially, the $i$-th element of the sequence is $i$.

Then follow $m$ lines, each containing two positive integers $l, r$, denoting the segment to reverse.

Output Format

Output one line with $n$ positive integers, which is the result after applying $m$ reversals to the original sequence.

5 3
1 3
1 3
1 4

4 3 2 1 5

Hint

Constraints
For $100\%$ of the testdata, $1 \le n, m \le 100000$, $1 \le l \le r \le n$.

Translated by ChatGPT 5