Problem Description

There is a sequence of length $ N $: $a_1,\ a_2,\ \ldots,\ a_N$. Initially, $a_i\ =\ i$.

You are given $ Q $ queries for this sequence.

The $ i $-th query is represented by three integers $t_i,\ x_i,\ y_i$, and their meanings are as follows:

• When $t_i\ =\ 1$, swap $ a_{x_i} $ and $a_{x_i\ +\ 1}$.
• When $t_i\ =\ 2$, sort $a_{x_i},\ a_{x_i\ +\ 1},\ \ldots\ a_{y_i}$ in ascending order.

Output the sequence $ a $ after processing all queries in order.

Input Format

The input is given from the standard input in the following format:

$ N $ $ Q $ $ t_1 $ $ x_1 $ $ y_1 $ $ t_2 $ $ x_2 $ $ y_2 $ $\vdots$ $ t_Q $ $ x_Q $ $ y_Q $

Output Format

Output the elements of $ a $ after processing all queries, separated by spaces.

Sample Input and Output

Sample Input #1

5 3
1 1 0
1 2 0
2 2 4

Sample Output #1

2 1 3 4 5

Sample Input #2

10 15
1 3 0
1 5 0
1 4 0
1 2 0
1 3 0
2 4 7
1 5 0
1 7 0
1 9 0
1 8 0
2 3 5
1 8 0
1 9 0
1 5 0
1 2 0

Sample Output #2

1 2 4 5 3 6 8 7 9 10

Notes/Hints

Constraints

• All inputs are integers.
• $2\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $1\ \leq\ Q\ \leq\ 2\ \times\ 10^5$
• $ t_i $ is either $ 1 $ or $ 2 $.
• When $t_i\ =\ 1$, $1\ \leq\ x_i\ <\ N$ and $y_i\ =\ 0$.
• When $t_i\ =\ 2$, $1\ \leq\ x_i\ <\ y_i\ \leq\ N$.

Sample Explanation 1

• After processing the 1st query, $ a $ becomes $2,\ 1,\ 3,\ 4,\ 5$.
• After processing the 2nd query, $ a $ becomes $2,\ 3,\ 1,\ 4,\ 5$.
• After processing the 3rd query, $ a $ becomes $2,\ 1,\ 3,\ 4,\ 5$.

见题面 Input 部分

见题面 Output 部分