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?
For this problem, you will be required to pass all the samples in order to receive points.
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 rsort the range in non-decreasing order.
2 l rsort the range in non-increasing order.
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