ADALIST  Ada and List
Ada the Ladybug has a TODOlist (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 TODOlist and number of queries.
Then a line with N numbers follows. Each number 0 ≤ A_{k} ≤ 10^{9} means k^{th} number in her TODOlist.
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 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
changyouren:
20211006 09:06:48
Treap 

pushpank09:
20191130 11:16:54


pushpank09:
20191130 10:55:40
Last edit: 20191130 11:23:18 

cgal1234:
20191020 14:47:47
@nikhil_more use http://spojtoolkit.com/


nikhil_more:
20191020 12:39:21
can someone provide testcases


ayush334:
20170918 19:10:44
easy problem


eagle750:
20170802 16:31:14
Getting tle on my 15th test case,can anyone help,submission id:19904139


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

kooljais24:
20170524 10:58:41
used STL.....AC 

hodobox:
20170419 23:21:53
Heh, tried out a nifty trick I once heard about, don't have to implement complicated structures ;) 
Added by:  Morass 
Date:  20160918 
Time limit:  6.5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU 