## ADALIST - Ada and List

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 ^{5},0 < Q < 5*10^{5}**, the number of elements in TODO-list and number of queries.

Then a line with **N** numbers follows. Each number **0 ≤ A _{k} ≤ 10^{9}** 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 ^{9}** (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 4816 32 7 1 2 4 8 16 32 712 4 8 16 32 7 2 4 8 16 32 7 4 8 16 32 748 16 32 7 4 8 16 32 666 7 4 8 16 326664 8 16 32 66648 16 32 666

hide comments

nikhil_ankam:
2017-04-05 19:09:44
@morass, I got TLE after 13th test case, can you help me, submission id: 19159915. |

Added by: | Morass |

Date: | 2016-09-18 |

Time limit: | 6.5s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: ASM64 GOSU |