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 ~N~ piles of acorns.

Each pile has some number of acorns: ~a_1, a_2, \dots, a_n~.

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

Each operation will be mixing up the order of the acorns of some range ~[l, r]~ 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.

~1 \le N,Q \le 200~
~1 \le a_i \le 10^9~
~1 \le l \le r \le N~

Input Specification

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

The second line will contain ~N~ integers on a single line, ~a_1, a_2, \dots, a_n~.

The next ~Q~ lines will be in the form

• 1 l r sort the range ~[l,r]~ in non-decreasing order.
• 2 l r sort the range ~[l,r]~ 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 ~N~ space separated integers. The ~i^\text{th}~ of these integers should be the number of acorns in the ~i^\text{th}~ 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