Reverse the subarray

Task

You are given an array $v$ of $n$ elements.
You need to perform $q$ operations, where operation $i$ represents reversing the subsequence $[l_i, r_i]$.

Input data

The first line contains two integers $n$ and $q$, representing the length of the array $v$ and the number of operations.
The second line contains $n$ numbers, representing the elements of the array $v$.
Each of the next $q$ lines contains 2 integers $l_i$ and $r_i$, representing the subsequence that will be reversed in operation $i$.

Output data

On a single line, print the elements of the array $v$ after applying the $q$ operations in the order they were read.

Constraints and notes

• $1 \leq n \leq 300\ 000$
• $1 \leq q \leq 200\ 000$
• $1 \leq v_i \leq 10^9$
• $1 \leq l_i \leq r_i \leq n$
• It is recommended to use the following line of code at the beginning of the main function, to reduce input data reading time: cin.tie(0)->sync_with_stdio(0);.

Example 1

stdin

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

stdout

1 5 1 7 4 2 2 

Explanation

The array $v$ is initially $[1, 5, 2, 1, 2, 4, 7]$.
After the first operation, the array $v$ becomes $[1, 5, \textbf{1, 2}, 2, 4, 7]$.
After the second operation, the array $v$ becomes $[1, 5, 1, \textbf{7, 4, 2, 2}]$.

Example 2

stdin

8 5
5 2 7 3 1 6 8 4
1 4
2 7
5 8 
1 8
2 3

stdout

5 7 2 4 1 6 8 3