Problem Description

Given a sequence $\left(a_{1}, a_{2}, \cdots, a_{n}\right)=(1,2, \cdots, n)$, that is, $a_{i}=i$.

Xiao Lan will perform $m$ operations on this sequence. Each operation is either sorting $a_{1}, a_{2}, \cdots, a_{q_{i}}$ in descending order, or sorting $a_{q_{i}}, a_{q_{i}+1}, \cdots, a_{n}$ in ascending order.

Please output the sequence after all operations are completed.

Input Format

The first line contains two integers $n, m$, representing the length of the sequence and the number of operations.

The next $m$ lines describe the operations. The $i$-th line contains two integers $p_{i}, q_{i}$, representing the operation type and parameter.

When $p_{i}=0$, it means sorting $a_{1}, a_{2}, \cdots, a_{q_{i}}$ in descending order.

When $p_{i}=1$, it means sorting $a_{q_{i}}, a_{q_{i}+1}, \cdots, a_{n}$ in ascending order.

Output Format

Output one line containing $n$ integers, separated by a single space, representing the sequence after all operations are completed.

3 3
0 3
1 2
0 2

3 1 2

Hint

[Sample Explanation]

The original sequence is $(1,2,3)$.

After step 1, it becomes $(3,2,1)$.

After step 2, it becomes $(3,1,2)$.

After step 3, it becomes $(3,1,2)$, the same as after step 2, because the first two numbers are already in descending order.

[Test Case Scale and Constraints]

For $30\%$ of the test cases, $n, m \leq 1000$.

For $60\%$ of the test cases, $n, m \leq 5000$.

For all test cases, $1 \leq n, m \leq 10^5$, $0 \leq p_{i} \leq 1$, $1 \leq q_{i} \leq n$.

Lanqiao Cup 2021, First Round Provincial Contest, Group B, Problem I.

Translated by ChatGPT 5