Array
Consider the array A that initially contains n numbers. Assume that the numbers in array are numbered from left to right, starting from one. Consider the following operations with this array.
I i x - insert value x after the number at position i, while all the numbers standing at positions greater than i are shifted to the right, and the length of array is increased by 1. The positions in the array are numbered from one. I 0 x means to add an element to the beginning of array, I 1 x means to add an element after the first number and so on.
D i - delete an element at position i. All the numbers standing at positions greater than i, are moved 1 position left, and the length of array is decreased by 1.
S
i[1] i[2]len - swap array blocks [i[1], ...,i[1]+ len] and [i[2], ...,i[2]+ len]. As a result of this operation must be swapped the values of the array A[i[1]] and A[i[2]], A[i[1]+ 1] and A[i[2]+ 1] and so on. It is guaranteed that the segments [i[1],i[1]+ len] and [i[2],i[2]+ len] do not overlap.A i - find what number is currently located at position i.
You have to perform all described operations.
Input
The first line contains the numbers n and m (1 ≤ n, m ≤ 100000), where m is the number of queries. Then n numbers are given - the array elements before operations. Next m lines contain the operations to execute. Each operation is given with a line where its type and parameters are given. It is guaranteed that during operations execution the array is usually not empty. The indexes in operations start from 1 till the current size of array, except the operation I 0 x, which corresponds to addition to the beginning of array. All input numbers range from 0 to 10^9.
Output
For each query A print the answer to it on a separate line. Besides, after all operations, print the resulting array.