Kth Largest Element In A Stream

You will be given a stream of numbers, and you need to find the kth largest number in the stream at any given time.

As the stream of numbers can not be given during compile time, so you need to design a data structure which can accept infinite numbers and can return the kth largest number at any given time.

The stream of numbers is nothing but a large collection of numbers from which integers are read at runtime, such as the user will never know the upper limit on the number of integers which will be read.

The implemented data structure must support the following operations:

1. add(DATA) :
   This function should take one argument of type integer 
   and store it in its pool.
2. int getKthLargest() :
   This function should return the kth largest number from 
   the current pool of integers.

You will be given q queries of 2 types:

1. 1 val - For this type of query, you need to insert the integer into your current pool of integers
2. 2 - For this type of query, you need to return the kth largest integer from the current pool of integers.

Note

 1. The maximum number of integers that will be given will always be under memory limits.
 2. You will also be given an initial pool of integers whose size will be equal to k.
 3. The maximum queries of type 1 will be less than 10^5.
 4. The kth largest element is not the kth distinct element but the kth largest element in the sorted order.
 5. There will be at least one query of type 2.

Input Format:

The first line contains two space-separated integers 'Q’ and ‘K’,  where Q denotes the number of queries which will be run against the implemented data structure.

The second line will contain ‘K’ space-separated integers which will be the initial pool of integers.

Then Q lines follow. The i-th line contains the i-th query in the format as in the problem statement

For the query of the first type, the input line will contain two integers ‘QUERYTYPE’ and ‘DATA’ separated by a single space, representing the type of the operation in integer and the integer data to be included in the pool respectively.

For the rest of the queries, the input line will contain only one integer value, representing the query being performed.

Output Format:

For Query-1, you do not need to return anything.

For Query-2, prints the kth largest integer from the current pool.

The output of each query of type 2 has to be printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given functions. 

Constraints:

1 <= Q <= 10 ^ 4
1 <= K <= 10 ^ 5
1 <= QUERYTYPE <= 2
1 <= DATA <= 10 ^ 9 

Time Limit: 1 sec.