Smallest Permutation by Reversal Operations

You are given an array \(a\) of \(n\) integers and \(m\) operations. Each operation is described by two integers \(l\) and \(r\) and indicates that you can reverse the subarray \(a[l\ldots r]\). You can perform any of the given operations an arbitrary number of times (including zero). Your task is to obtain the lexicographically smallest permutation of the array that is possible under these operations.

Note: In this problem, the allowed operations are such that the lexicographically smallest permutation is always the sorted order of the array. In other words, regardless of the operations provided, the answer is \(sorted(a)\).

Constraints:

• \(1 \leq n \leq 10^5\)
• \(0 \leq m \leq 10^5\)
• The elements of \(a\) are integers.

Input/Output: The input is read from standard input and the output is written to standard output.

inputFormat

The input is given in the following format from stdin:

n m
a[0] a[1] ... a[n-1]
l1 r1
...
lm rm

Here:

• \(n\) is the number of elements in the array.
• \(m\) is the number of operations.
• The next line contains \(n\) space-separated integers representing the array \(a\).
• Then follow \(m\) lines, each containing two space-separated integers \(l\) and \(r\) (1-indexed) representing an operation.

outputFormat

Output the lexicographically smallest permutation of the array as a sequence of \(n\) space-separated integers on a single line to stdout.

## sample

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

1 2 3 4 5