#COUNT1IT. Ghost Town
Ghost Town
You are given n numbers initially. You have to maintain a multiset for those n numbers. Then you are given q queries. Queries will be one of the following types -
- 1 x : Let a be the count of elements smaller than or equal to x. Add x+a into the multiset.
- 2 y : report the number of numbers in the multiset that are smaller than or equal to y.
- 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^9-2*10^5)
1<=y,z<=10^9
1<=Initial elements of the multiset<=(10^9-2*10^5)
Input
The first line will contain two integers, n and q, denoting the number of initial 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 an 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</p>Output: 11 12 10 invalid 15 invalid 7 12 invalid 8 invalid 8