Массив

Рассмотрим массив A, который изначально состоит из n чисел. Предположим, что числа в массиве нумеруются слева направо, начиная с единицы. Рассмотрим следующие операции с этим массивом.

• I i x - вставить число x после числа, стоящего на позиции i, при этом все числа, стоявшие на позициях, больших i, сдвигаются вправо, и длина массива увеличивается на 1. Позиции в массиве нумеруются с единицы. I 0 x обозначает добавить элемент в начало массива, I 1 x обозначает вставить элемент после первого числа и т.д.

• D i - удалить элемент, стоящий на позиции i. При этом все числа, стоявшие на позициях, больших i, сдвигаются на 1 влево, и длина массива уменьшается на 1.

• S i[1] i[2] len - поменять местами блоки массива [i[1], ..., i[1] + len] и [i[2], ..., i[2] + len]. В результате этой операции должны поменяться значениями элементы массива A[i[1]] и A[i[2]], A[i[1] + 1] и A[i[2] + 1], и т.д. Гарантируется, что отрезки [i[1], i[1] + len] и [i[2], i[2] + len] не пересекаются.

• A i - узнать, какое число находится в данный момент на позиции i.

Вам предстоит выполнить все описанные операции.

Входные данные

В первой строке содержатся числа n и m (1 ≤ n, m ≤ 100000), где m - количество запросов. Далее следует n чисел - элементы массива до выполнения каких либо операций. Следующие m строк содержат операции, которые необходимо выполнить. Каждая операция задается строкой, обозначающей вид операции, и затем её параметрами, перечисленными через пробел. Гарантируется, что в процессе выполнения операций массив всегда будет не пустым. Все индексы, которые используются в операциях, будут в пределах от 1 до текущего размера массива, за исключением операции I 0 x, которая соответствует добавлению в начало массива. Все входные числа от 0 до 10^9.

Выходные данные

На каждый запрос A выведите ответ на него в отдельной строке. Кроме того, после выполнения всех операций выведите результирующий массив.

Примеры