Segment Sorting Operations

You are given a sequence of ( n ) positive integers ( a_1, a_2, \dots, a_n ). You need to perform ( m ) operations. In each operation, you are given two integers ( l ) and ( r ) (with ( l \leq r )). For each operation, you must sort the subarray ( a_l, a_{l+1}, \dots, a_r ) in ascending order. Note that each operation is applied on the result of the previous operations. After all operations are performed, output the final sequence.

inputFormat

The first line contains two integers ( n ) and ( m ), representing the number of elements in the sequence and the number of operations respectively. The second line contains ( n ) space-separated positive integers, the elements of the sequence. This is followed by ( m ) lines, each containing two space-separated integers ( l ) and ( r ) (( 1 \leq l \leq r \leq n )), indicating the segment to sort in ascending order.

outputFormat

Output the final sequence after all operations. The sequence should be printed as ( n ) space-separated integers on a single line.

sample

5 2
5 3 2 4 1
2 4
1 5

1 2 3 4 5