Queries

Kunal likes numbers and today he has an list of N integers.Sunny likes to ask a lot questions and he saw Kunal with his list of integers and instantly decided to ask Kunal q number of queries.Each query can be of the following:

A Y - Add the integer Y to the list.
M - Print the maximum integer from the list and remove it from the list.
m - Print the minimum integer from the list and remove it from the list.

Note: if there are multiple occurences of maximum/minimum number, you can remove any one of them

Help Kunal answer this queries quickly.

Input Format

First line contains two integers N and q denoting the size of the list of numbers with Kunal and number of queries Sunny will ask respectively.
Next line contains N space separated integers Xi, the integers of the list.
q lines follow with one of the three types of queries mentioned in the problem statement.

1<=N<=105
1<=q<=105
1<=Xi , Y<=109

Before any m or M type queries, it is guaranteed that the size of the list would be atleast one and also not exceed 105 considering all the queries of type A Y

Output Format

For each query of type M and m, print the answer to that query on a new line.

Sample Input

10 6
13 12 999 14 15 16 19 18 17 110
m
A 1000
M
M
A 10
m

Sample Output

12
1000
999
10

Explanation

Initially the list is [13, 12, 999, 14, 15, 16, 19, 18, 17, 110]

First query is m, print the minimum and remove it from the list.
We print 12 and remove it after which our list is [13, 999, 14, 15, 16, 19, 18, 17, 110]

Second query is A 1000, we add it to the list after which our list is [13, 999, 14, 15, 16, 19, 18, 17, 110 , 1000]

Third query is M print the maximum and remove it from the list.
We print 1000 and remove it after which our list is [13, 999, 14, 15, 16, 19, 18, 17, 110]

Fourth query is M print the maximum and remove it from the list.
We print 999 and remove it after which our list is [13, 14, 15, 16, 19, 18, 17, 110]

Fifth query is A 10, we add it to the list after which our list is [13, 14, 15, 16, 19, 18, 17, 110 , 10]

Sixth query is m, print the minimum and remove it from the list.
We print 10 and remove it after which our list is [13, 14, 15, 16, 19, 18, 17, 110]

source code in python:

import bisect

n,m = [int(x) for x in input().split()]

t=[];

r=[];

y=[int(x) for x in input().split()]

y.sort();

for i in range(m):

        r=input().split();

        if r[0]=='m':

              print(y.pop(0));

        elif r[0]=='M':

              print( y.pop());

        else:

             bisect.insort(y,int(r[1]));

              

output:

Input (stdin)

10 6
13 12 999 14 15 16 19 18 17 110
m
A 1000
M
M
A 10
m

Your Output (stdout)

12
1000
999
10

Expected Output

12
1000
999
10

test case 2:

Input (stdin)
6 2
629321215 11361548 817039529 786899840 231603078 594823668
A 718761252
M

Your Output (stdout):

817039529
Expected Output
817039529