Массив
Массив
Рассмотрим массив A, который изначально состоит из n чисел. Предположим, что числа в массиве нумеруются слева направо, начиная с единицы. Рассмотрим следующие операции с этим массивом.
- I i x - вставить число x после числа, стоящего на позиции i, при этом все числа, стоявшие на позициях, больших i, сдвигаются вправо, и длина массива увеличивается на 1. Позиции в массиве нумеруются с единицы. I 0 x обозначает добавить элемент в начало массива, I 1 x обозначает вставить элемент после первого числа и т.д.
- D i - удалить элемент, стоящий на позиции i. При этом все числа, стоявшие на позициях, больших i, сдвигаются на 1 влево, и длина массива уменьшается на 1.
- S
i1 i2
len - поменять местами блоки массива [i1
, ...,i1
+ len] и [i2
, ...,i2
+ len]. В результате этой операции должны поменяться значениями элементы массива A[i1
] и A[i2
], A[i1
+ 1] и A[i2
+ 1], и т.д. Гарантируется, что отрезки [i1
,i1
+ len] и [i2
,i2
+ len] не пересекаются. - A i - узнать, какое число находится в данный момент на позиции i.
Вам предстоит выполнить все описанные операции.
Входные данные
В первой строке содержатся числа n и m (1 ≤ n, m ≤ 100000), где m - количество запросов. Далее следует n чисел - элементы массива до выполнения каких либо операций. Следующие m строк содержат операции, которые необходимо выполнить. Каждая операция задается строкой, обозначающей вид операции, и затем её параметрами, перечисленными через пробел. Гарантируется, что в процессе выполнения операций массив всегда будет не пустым. Все индексы, которые используются в операциях, будут в пределах от 1 до текущего размера массива, за исключением операции I 0 x, которая соответствует добавлению в начало массива. Все входные числа от 0 до 109
.
Выходные данные
На каждый запрос A выведите ответ на него в отдельной строке. Кроме того, после выполнения всех операций выведите результирующий массив.
5 6 1 2 3 4 5 I 0 10 A 1 A 6 D 3 A 3 S 1 4 1
10 5 3 4 5 3 10 1