For an array $A$ of $n$ integers, you need to process $q$ queries, each belonging to one of the three types:
- `1 x`: Add the value $x$ to the end of array $A$.
- `2`: Remove the last value from array $A$. It is guaranteed that $A$ has at least one element at this point.
- `3 k`: Find the element with index $k$ in the array, array indices starting from $1$.
### Input
- The first line consists of two integers $n, q$.
- The second line contains $n$ integers $A_i$.
- The next $q$ lines, each containing a query in the specified format.
### Output
- Output an integer as the answer for each type $3$ query.
### Constraints
- $1 \le n, q \le 10^5$.
- $1 \le x \le 10^9$.
- $1 \le k \le |A|$ where $|A|$ is the length of array $A$ at the time of the query.
### Sample test
Input
```
5 4
1 2 3 4 5
1 6
3 6
2
3 2
```
Output:
```
6
2
```
