Boring Data Structure

Problem Description

Firdavs started studying data structures, in particular those that allow performing operations on segments and answering queries about the value of an element at a given position. To make it more interesting for Firdavs, Khaled complicated the task by adding a query to swap two elements at different positions. Firdavs was able to solve this problem --- can you?

You are given numbers $N$, $Q$, and an array $A$ of size $N$. Write a program that processes $Q$ operations of the following types:

• $1\; i$ --- output the value of the element at position $i$;
• $2\; i\; j$ --- swap the values of the elements at positions $i$ and $j$;
• $3\; l\; r\; x$ --- increase by all elements in the segment from to inclusive.

Input

In the first line, there are two integers $N$ and $Q$ $(2 \le N, Q \le 3 \cdot 10^5)$.

In the second line, the elements of the array are written $A_1,\; A_2,\; \ldots,\; A_N$ $(1\le A_i\le$.

In the next $Q$ lines, the operations are given in the following format:

• $1\; i$ $(1 \le i \le N)$ --- query for the value of the element at position $i$;
• $2\; i\; j$ $(1\le i,j\le N,i$ --- swap the values of the elements at positions and ;

Output

For each query of type $1$, output the value of the element at position $i$ on a separate line.

Scoring System

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

2025
2026