Module: cartesian tree


Problem

2 /3


Another task about queries in an array

Problem

You are given an array a of size n and q queries to it. There are two types of requests:
  • li ri — perform a cyclic shift of the segment [li, ri] to the right. That is, for every x such that li ≤ x  < riax + 1 becomes equal to the previous value ax and ali becomes equal to the previous value  ;ari;
  • li ri — flip the segment [li, ri].
 
It is necessary to output the array after all requests have been processed.
 
Input
The first line contains two integers n and q (1 ≤ n, q  ≤ 2·105).
The second line contains n integers a1a2< /sub>, ..., an (1 ≤ ai ≤ 109).
Next come q lines. The ith of them contains three integers tili ri, where ti — type ith query, [li, ri] — segment on which the query is executed (1 ≤ ti ≤ 2, 1 ≤ l< sub>i
 ≤ ri ≤ n).< br />  
Imprint
Print m numbers, ith of which is equal to the number at position bi  ;after all requests have been processed.

Enter Output
6 3
1 2 3 4 5 6
2 1 3
2 3 6
1 1 6
1 3 2 6 5 4


(c) Kurbatov E., 2018