Reverse the subarray

Time limit: 1.5s Memory limit: 128MB Input: Output:

Task

You are given an array vv of nn elements.
You need to perform qq operations, where operation ii represents reversing the subsequence [li,ri][l_i, r_i].

Input data

The first line contains two integers nn and qq, representing the length of the array vv and the number of operations.
The second line contains nn numbers, representing the elements of the array vv.
Each of the next qq lines contains 2 integers lil_i and rir_i, representing the subsequence that will be reversed in operation ii.

Output data

On a single line, print the elements of the array vv after applying the qq operations in the order they were read.

Constraints and notes

  • 1n300 0001 \leq n \leq 300\ 000
  • 1q200 0001 \leq q \leq 200\ 000
  • 1vi1091 \leq v_i \leq 10^9
  • 1lirin1 \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);.
# Score Constraints
0 0 Examples
1 20 1n,q5 0001 \leq n, q \leq 5\ 000
2 20 1n,q100 0001 \leq n, q \leq 100\ 000
3 60 No additional constraints

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 vv is initially [1,5,2,1,2,4,7][1, 5, 2, 1, 2, 4, 7].
After the first operation, the array vv becomes [1,5,1, 2,2,4,7][1, 5, \textbf{1, 2}, 2, 4, 7].
After the second operation, the array vv becomes [1,5,1,7, 4, 2, 2][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 

Log in or sign up to be able to send submissions!