Problem statement

Given an array $A$ of $N$ integers. Answer $Q$ queries of the type $(l, r)$ - reverse the subarray $A[l...r]$. Print the array after each query.

Input format The first line contains two integers $N$ and $Q$ $(1 \leq N, Q \leq 10^3)$.

The second line contains $N$ space-separated integers representing the array $A[]$ $(1 \leq A[i] \leq 10^6)$.

Next, $Q$ lines each contains pair of integers $l$ and $r$ $(1 \leq l \leq r \leq N)$.

---

Sample

Input

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

Output

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

---

Solution

For each query, we can reverse the given array in $O(N)$ time. Let’s see how we would reverse the entire array; we can then do the same to reverse a subarray.

We start with two pointers, one at the start and one at the end of the array. Pointer 1 moves to the right and Pointer 2 moves to the left after each step. At each step, we swap the elements at the two pointers.

See the below illustrations for better understanding.