TEMPLEQ - Temple Queues


main-destinations-tirupati

The Tirumala temple is the most visited place of worship in the world. As the number of pilgrims who visit the temple each day is very high, the head of the temple should keep monitoring the queue system. Today is another lovely day and he has started his work. There are N queues at the entrance of the temple and some of them are already filled with pilgrims. Each queue has a metal door at the beginning, which leads to the temple. When the door is opened, it allows only one pilgrim to get through it and it gets closed immediately after that.

New pilgrims are rushing in to the queues and the head needs to monitor the current sizes of the queues and decide which doors to be opened. At any time, he wants to know how many queues currently have at least X pilgrims. He also decides an integer Y and wants to open the doors of all the queues having at least Y pilgrims at that time. You are the controller of the queue system and are following his instructions. Respond quickly and win yourself a big laddu (sweet) from him :) .


Read the input section for rest of the details.

Input

The first line contains two integers N and Q. N - The number of queues [ 1 <= N <= 100,000 ], Q - The number of queries [ 0 <= Q <= 500,000 ] . The second line contains N integers, which are the initial sizes of the queues. ith integer ( 1-based ) is the initial size of queue i [ 0 <= initial size <= 100,000,000 ]

Each of the next Q lines is one of the following

1 A [ One pilgrim enters the queue# A ( 1 <= A <= N ) ]

2 X [ Find the number of queues having atleast X pilgrims currently ( 0 <= X <= 1,000,000,000 ) ]

3 Y [ Open the doors of all the queues having atleast Y pilgrims ( 1 <= Y <= 1,000,000,000 ), and thus allowing only one pilgrim to enter the temple from each of them ]

Output

For each query of type "2 X" , print the answer in a new line.

Example

Input:
5 6
20 30 10 50 40
2 31
1 2
2 31
3 11
2 20
2 50

Output:
2
3
3
0

Note : Ideal time limit should be 2s. It has been increased to 7s, to let Java solutions pass, as the i/o is huge.

* There are multiple test sets, and the judge shows the sum of the time taken over all test sets of your submission, if Accepted.

hide comments
linkret: 2019-04-02 10:33:41

yes mobile phone programming is so fun :D

gabrijel: 2019-03-30 17:20:26

I solved this problem in a bus on a mobile phone!!! Ez AC in 3 hours

be1035016: 2018-06-14 21:32:13

nice question.coding part was bit tricky.O(n+q)logn.

arpit728: 2018-05-06 09:07:34

Not a single accepted solution using java

sanyam123: 2018-01-26 07:15:37

Caution: using fast i/o gives wrong answer on 3 test case where as submitting same code with printf/scanf gives AC in c++

vagesh_verma: 2017-02-26 20:12:22

(N+Q)log(N) solution..

Abhinandan Agarwal: 2017-02-26 13:48:15

my complexity - C*(n+q). C is around 30 .

ashish kumar: 2015-12-16 08:15:33

I am getting WA please check my solution or provide some testcases ?

sayantan ghosh: 2015-07-28 15:14:53

can someone provide good testcases?I am getting wa.

Jannatul Ferdows Jenny: 2015-07-08 13:12:16

Very unique problem. Kudos to setter.


Added by:Anil Kishore
Date:2011-02-25
Time limit:0.935s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:CodeMutants 2011 , DA-IICT, India