Segment Sorting Operations

You are given an array of n integers, and you need to perform m sorting operations on it. In each operation, you are given two integers l and r (1-indexed), and you need to sort the segment from position l to r in non-decreasing order. After performing all operations, output the resulting array.

Note: The indices are 1-indexed. Each sorting operation works on the current state of the array.

Example:

Input:
5 2
10 5 3 6 2
1 3
2 5
Output:
3 2 5 6 10

</p>

inputFormat

The first line consists of two space-separated integers n and m:

• n is the number of elements in the array.
• m is the number of operations.

The second line contains n space-separated integers representing the initial array.

Each of the next m lines contains two space-separated integers l and r, representing the left and right indices (inclusive) of the segment to sort.

outputFormat

Output a single line containing the final array after all sorting operations. The elements should be separated by a space.

## sample

5 2
10 5 3 6 2
1 3
2 5

3 2 5 6 10

</p>