COUNT1IT - Ghost Town

no tags 

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^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 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.

 

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

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
c650: 2016-11-20 19:21:14

Getting WA here but I am matching the test case. Any catches to look out for?
RE: I don't think you'll have to handle any corner cases.

Last edit: 2016-12-08 04:39:02
anonymous: 2016-10-12 15:27:59

The initial content of array is not described in the input section. It is
quite clear from example how input will look like, but it would be nice to
describe it in input section.
RE: Updated!

Last edit: 2016-10-14 19:30:51
SnowFire: 2016-10-12 12:15:51

Why did you disqualify my solution?
RE: sorry for inconvenience, I updated the test cases, didn't know how to rejudge your solution. Your solution would give Seg fault on the updated test data. :-) . Sorry for disqualifying.

Last edit: 2016-10-12 14:58:33
bwtzakippp: 2016-10-11 16:58:36

test

geeta: 2016-10-10 21:05:09

Last edit: 2016-10-12 09:42:16
[Rampage] Blue.Mary: 2016-10-10 15:34:53

What's the range of the numbers in the initial array? [1,10^9]?

[Edited After AC] I assume that all numbers in the multiset are in range [0, 2^31-1] (i.e. non-negative 32-bit signed integers.)
RE: The elements in the initial array are between 1 and 10^9-2*10^5. I have kept the constraints carefully, so that the numbers that will be inserted in the multiset during the course of action won't exceed 10^9.

Last edit: 2016-10-11 18:58:05
[Rampage] Blue.Mary: 2016-10-10 15:34:51

Last edit: 2016-10-10 15:51:35

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