E. The Highlanders' Tournament
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In ancient times, which no one remembers, a Highlanders' tournament was held. This tournament was not a sport event rather it was a matter of life or death! Still, it was meant as a manifestation of life! The tournament was attended by n highlanders lined up in a row. Each fighter was endowed with strength! The strength of the i-th highlander was determined by the value of pi. We should note that there were no highlanders with the same level of strength. The tournament itself was held in m stages. Before the start of each battle, the great leader Gyda chose several consecutive highlanders from the row. The selected group began the battle, where everyone fought for himself. The strongest fighters won the battle. After the battle, the winner stood back into his own place in the line, then the line closed and the fighters again stood shoulder to shoulder.

You need to state the strength of the fighters in the row after the end of the tournament.

Input

The first line contains two integers n and m. n is the number of highlanders fighting in the tournament (1 ≤ n ≤ 2·105). m is the number of battles (1 ≤ m ≤ 105).

The next line contains the strength indicators pi of each fighter (1 ≤ pi ≤ 109).

The next m lines contain pairs of numbers l and r (l ≤ r), which specify the range of numbers of the fighting highlanders in the row.

Output

State the strength of the fighters after the end of the tournament.

Examples
Input
7 4
48 1 57 25 69 26 88
1 2
2 3
2 5
1 2
Output
88
Input
10 3
8 27 4 1 9 2 10 66 43 13
1 4
1 2
2 4
Output
27 66 43 13