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 kth number, sometimes she inserts something on kth position and sometime she asks for kth 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 ≤ 105,0 < Q < 5*105, the number of elements in TODO-list and number of queries.

Then a line with N numbers follows. Each number 0 ≤ Ak ≤ 109 means kth 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 ≤ 109 (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 kth 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


hide comments
ayush334: 2017-09-18 19:10:44

easy problem

eagle750: 2017-08-02 16:31:14

Getting tle on my 15th test case,can anyone help,submission id:19904139

anubhav1772: 2017-07-17 11:16:26

Got TLE while implementing using ArrayList in java but AC in CPP...although not satisfied with time taken :(

kooljais24: 2017-05-24 10:58:41

used STL.....AC

hodobox: 2017-04-19 23:21:53

Heh, tried out a nifty trick I once heard about, don't have to implement complicated structures ;)

nikhil_ankam: 2017-04-06 12:18:21

@morass actually I found some error in my code which I didn't handle well, I have to change my approach. Anyways thanks for your reply :)

morass: 2017-04-05 21:46:24

@nikhil_ankam: Good day to you

Firstly, you get TLE at first test-case (even though a TC fails, it runs all of them, so it might look like that)

Secondly, it loops (forever) in following cycle:

for (map<int,int>::iterator it=nemE.upper_bound(k);
it!=nemE.end(); ++it){
upd = false;
nemE.insert(make_pair(it->first+1, it->second));
nemE.erase(it);
}

(so you can make conclusion from it) :)

Good Luck & Have Nice Day!

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