COUNT1IT  Ghost Town
You are given n numbers initially. You have to maintain a multiset for those n numbers. Then you are given q queries. Qeuries will be one of the following types 
1) 1 x : Let a be the count of elements smaller than or equal to x. Add x+a into the multiset.
2) 2 y : report the number of numbers in the multiset that are smaller than or equal to y.
3) 3 z : report the zth smallest number of the multiset. Note that if any number d appears more than once, it is to be counted as many times it appears! Also, if z exceeds the number of elements in the multiset, that is answer for this query doesn't exist, print "invalid". Look at the sample input for clarification.
Note:
since it is a multiset, it will also store duplicates. Also, lets say our multiset has elements 1,2,2,3,3,3. then for z=3, answer would be 2 .
Constraints
1<=n<=100000
1<=q<=100000
1<=x<=(10^92*10^5)
1<=y,z<=10^9
1<=Initial elements of the multiset<=(10^92*10^5)
Input
The first line will contain two integers, n and q, denoting the number of initially members of the multiset and the number of queries.
Next q lines will be of he form 
Type D : That is, the queries will be of the one of given 3 types and accordingly, you will be given and integer D.
Output
You have to print the output for query numbers 2 and 3.
Example
Input:10 20
7 35 44 25 15 10 21 42 12 33
1 6
1 39
2 47
2 96
1 29
2 40
3 27
3 5
1 22
1 44
3 32
1 28
3 2
2 39
3 23
2 31
1 13
1 50
3 38
2 26
Output:11
12
10
invalid
15
invalid
7
12
invalid
8
invalid
8
hide comments
Abhinandan Agarwal:
20210927 18:29:19
@DK  spoj runs multiple tests in parallel. You may have got the final verdict when spoj may have spawned test 11. That may be one answer.


mhasan01:
20200706 21:00:14
Accepted using Treap on One Go :) 

DK...:
20191226 20:20:55
wtf with this problem, i tried solutions with treap or splay and all of them got TL test 11, i tried very hard optimizacions and all of them again got TL, I sent a solucion with brute force just for n=10 and q=20 and for all other testcases i printed "shit problem" and i got TL test 11. I hash all the given input and print the given answer and for all other testcases i printed "shit problem" and again i got TL, @Abhinandan Agarwal, is your problem OK? Can you explain wtf is happening?


frochbg:
20190722 11:01:10
Great problem with treap :) 

c650:
20161120 19:21:14
Getting WA here but I am matching the test case. Any catches to look out for?


anonymous:
20161012 15:27:59
The initial content of array is not described in the input section. It is


SnowFire:
20161012 12:15:51
Why did you disqualify my solution?


bwtzakippp:
20161011 16:58:36
test 

geeta:
20161010 21:05:09
Last edit: 20161012 09:42:16 

[Rampage] Blue.Mary:
20161010 15:34:53
What's the range of the numbers in the initial array? [1,10^9]?

Added by:  Abhinandan Agarwal 
Date:  20161010 
Time limit:  0.5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU 
Resource:  My own problem 