SPOJ.com - Problem COUNT1IT

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

Output:
11
12
10
invalid
15
invalid
7
12
invalid
8
invalid
8

Submit solution!

hide comments



	Abhinandan Agarwal: 2021-09-27 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. The test cases are fine, there are multiple accepted solutions. Let me know how I can help you.
	mhasan01: 2020-07-06 21:00:14 Accepted using Treap on One Go :)
	DK...: 2019-12-26 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: 2019-07-22 11:01:10 Great problem with treap :)
	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
	[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-210^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*

Submit solution!

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