Ada the Ladybug has a TODO-list (containing only numbers - for simplicity). She is still doing something, so she sometimes erases k^th number, sometimes she inserts something on k^th position and sometime she asks for k^th number.

Sadly, she is now searching for a work at position k so she doesn't have time to do this herself. Can you help her?

Input

The first line will contain 0 < N ≤ 10⁵,0 < Q < 5*10⁵, the number of elements in TODO-list and number of queries.

Then a line with N numbers follows. Each number 0 ≤ A_k ≤ 10⁹ means k^th number in her TODO-list.

Afterward, Q lines follow, each beginning with number 1 ≤ a ≤ 3

1 k x means that you will add number x to position k

2 k means that you will erase number from position k

3 k means that you will print number from position k

For all queries, it is true that 1 ≤ k ≤ #SizeOfList, 0 ≤ x ≤ 10⁹ (for query 1, it can be also put to position #SizeOfList + 1)

You will never get query of type 2 or 3 if the list is empty

Output

For each query of type 3, print k^th numbers

Example Input

6 10
1 2 4 8 16 32
3 4
1 1 7
3 2
2 2
2 2
3 2
1 6 666
3 6
2 1
3 1

Example Output

8
1
4
666
4

Queries explanations

1 2 4 8 16 32
7 1 2 4 8 16 32
7 1 2 4 8 16 32
7 2 4 8 16 32
7 4 8 16 32
7 4 8 16 32
7 4 8 16 32 666
7 4 8 16 32 666
4 8 16 32 666
4 8 16 32 666