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

• I i x - вставить число x после числа, стоящего на позиции i, при этом все числа, стоявшие на позициях, больших i, сдвигаются вправо, и длина массива увеличивается на 1. Позиции в массиве нумеруются с единицы. I 0 x обозначает добавить элемент в начало массива, I 1 x обозначает вставить элемент после первого числа и т.д.
• D i - удалить элемент, стоящий на позиции i. При этом все числа, стоявшие на позициях, больших i, сдвигаются на 1 влево, и длина массива уменьшается на 1.
• Si1 i2len - поменять местами блоки массива [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 выведите ответ на него в отдельной строке. Кроме того, после выполнения всех операций выведите результирующий массив.