P8747 [Lanqiao Cup 2021 NOI Qualifier B] Bidirectional Sorting

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.

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 one line containing $n$ integers, separated by a single space, representing the sequence after all operations are completed.

**[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