While walking through the forest on his daily strolls, Zeyu happened to find a squirrel. Out of curiosity, he decided to follow the squirrel until he stumbled upon its piles of acorns.

Each pile has some number of acorns: .

Since he is feeling particularly zany, while the squirrel is gone to fetch more acorns he will perform a series of operations.

Each operation will be mixing up the order of the acorns of some range in either non-decreasing order or in non-increasing order.

Can you help Zeyu determine the final order of the piles of acorns?

#### Constraints

**For this problem, you will be required to pass all the samples in order to receive points.**

#### Input Specification

The first line will contain , the number of piles of acorns and , the number of operations to be performed.

The second line will contain integers on a single line, .

The next lines will be in the form

`1 l r`

sort the range in non-decreasing order.`2 l r`

sort the range in non-increasing order.

#### Output Specification

**This problem is graded with an identical checker. This includes whitespace characters. Ensure that every line of output is terminated with a \n character and that there are no trailing spaces.**

On a single line, output space separated integers. The of these integers should be the number of acorns in the pile after all operations.

#### Sample Input 1

```
5 3
1 2 3 4 5
2 2 4
1 1 3
1 3 5
```

#### Sample Output 1

`1 3 2 4 5`

#### Explanation of Sample Output 1

The state of the array after each operation

```
1 4 3 2 5
1 3 4 2 5
1 3 2 4 5
```

## Comments