Description

As described, you need to maintain an array of length $N$, supporting the following two operations:

1. Modify the value at some position on a certain historical version.
2. Access the value at some position on a certain historical version.

In addition, each time you perform an operation, a new version is created. The version number equals the current operation index (starting from $1$; version $0$ is the initial array).

For operation $2$, a completely identical version is created without any changes. That is, the version generated by a query is a copy of the version that is being accessed.

Input Format

The first line contains two positive integers $N, M$, the array length and the number of operations.

The second line contains $N$ integers, the initial values of the array (denoted as $a_i$, $1 \leq i \leq N$).

Each of the next $M$ lines contains $3$ or $4$ integers, representing one of the two operations (assume the current operation is the $i$-th):

1. For operation $1$, the format is v 1 p c, meaning: based on version $v$, set $a_p$ to $c$.
2. For operation $2$, the format is v 2 p, meaning: access the value of $a_p$ in version $v$. Note: the version that is duplicated must be $v$.

Output Format

Output several lines, each being the result of an operation $2$, in order.

5 10
59 46 14 87 41
0 2 1
0 1 1 14
0 1 1 57
0 1 1 88
4 2 4
0 2 5
0 2 4
4 2 1
2 2 2
1 1 5 91

59
87
41
87
88
46

Hint

Constraints

• For $30\%$ of the testdata, $1 \leq N, M \leq 10^3$.
• For $50\%$ of the testdata, $1 \leq N, M \leq 10^4$.
• For $70\%$ of the testdata, $1 \leq N, M \leq 10^5$.
• For $100\%$ of the testdata:
  • $1 \leq N, M \leq 10^6$;
  • $1 \leq p \leq N$;
  • Suppose this is the $x$-th operation, then $0 \leq v < x$;
  • $-10^9 \leq a_i, c \leq 10^9$.

Sample Explanation

After all operations, a total of $11$ versions are generated, numbered $0 \sim 10$, in order:

Version $0$: 59 46 14 87 41. Version $1$: 59 46 14 87 41. Version $2$: 14 46 14 87 41. Version $3$: 57 46 14 87 41. Version $4$: 88 46 14 87 41. Version $5$: 88 46 14 87 41. Version $6$: 59 46 14 87 41. Version $7$: 59 46 14 87 41. Version $8$: 88 46 14 87 41. Version $9$: 14 46 14 87 41. Version $10$: 59 46 14 87 91.

Translated by ChatGPT 5