Скучная Структура Данных

Описание задачи

Фирдавс начал изучать структуры данных, в частности те, которые позволяют выполнять операции на отрезках и отвечать на запросы о значении элемента в заданной позиции. Чтобы Фирдавсу не было скучно, Халед усложнил задачу, добавив запрос на обмен двух элементов в разных позициях. Фирдавс смог решить эту задачу --- сможете ли вы?

Вам даны числа $N$, $Q$ и массив $A$ размера $N$. Напишите программу, которая обрабатывает $Q$ операций следующих типов:

• $1\; i$ --- вывести значение элемента на позиции $i$;
• $2\; i\; j$ --- поменять местами значения элементов в позициях $i$ и $j$;
• $3\; l\; r\; x$ --- увеличить на все элементы на отрезке от до включительно.

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

В первой строке даны целые числа $N$ и $Q$ $(2 \le N, Q \le 3 \cdot 10^5)$.

Во второй строке записаны элементы массива $A_1,\; A_2,\; \ldots,\; A_N$ $(1\le A_i\le {}^{}$.

В следующих $Q$ строках заданы операции в следующем формате:

• $1\; i$ $(1 \le i \le N)$ --- запрос значения элемента на позиции $i$;
• $2\; i\; j$ $(1\le i,j\le N,i$ --- обменять значения элементов в позициях и ;

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

Выведите для каждого запроса типа $1$ значение элемента в позиции $i$ в отдельной строке.

Система оценки

2 5
26 26
3 1 2 1999
3 1 1 1
2 1 2
1 1
1 2

2025
2026