Dòng Thời Gian Của Mảng

Một mảng gồm $n$ phần tử được xem là phiên bản $0$. Sau đó có $m$ thao tác, đánh số từ $1$ đến $m$; thao tác thứ $i$ luôn tạo ra phiên bản $i$.

Mỗi thao tác chọn một phiên bản $v$ đã tồn tại và thuộc một trong hai loại:

• $v$ $1$ $p$ $x$: phiên bản $i$ ban đầu giống phiên bản $v$, sau đó phần tử ở vị trí $p$ được đổi thành $x$.
• $v$ $2$ $p$: in phần tử ở vị trí $p$ của phiên bản $v$; phiên bản $i$ là một bản sao không thay đổi của phiên bản $v$.

Vì thao tác đọc cũng tạo phiên bản, mọi phiên bản từ $0$ đến $i$ đều có thể được tham chiếu trong các thao tác về sau.

Input

• Dòng đầu chứa hai số nguyên $n$ và $m$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$, là phiên bản $0$.
• Mỗi dòng trong $m$ dòng tiếp theo mô tả một thao tác theo một trong hai dạng $v$ $1$ $p$ $x$ hoặc $v$ $2$ $p$.

Output

• Với mỗi thao tác loại $2$, in giá trị được đọc trên một dòng.

Constraints

• $1\le n,m\le 10^6$.
• $-10^9\le a_i,x\le 10^9$.
• $1\le p\le n$.
• Ở thao tác thứ $i,0\le v<i$.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n,m\le 2000$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

4 6
5 8 2 9
0 2 2
0 1 3 7
2 2 3
1 1 2 -4
4 2 2
2 2 2

8
7
-4
8