Gem Management System

GY bought a batch of gems and stored them in a warehouse. One day, he decided to take an inventory and removed all m gems from the warehouse to put them into a gem management system. Each gem i has a precious value \(v_i\). He wants you to build a program that can find the \(n^{th}\) most precious gem when sorted in descending order (i.e. the gem with the \(n^{th}\) highest value). However, some gems were accidentally left behind in the warehouse and may be added to the system later. Although the number of these additional gems is small, he still wants the system to work correctly.

The input begins with two integers m and q, where m is the number of gems initially added to the system and q is the number of operations to process. The next line contains m integers representing the values of the gems. Each of the following q lines represents an operation in one of the following two formats:

• 1 n: Query for the nth most precious gem in the current system.
• 2 x: Add a gem with value x into the system.

It is guaranteed that for every query operation 1 n, \(n\) will not exceed the current number of gems in the system.

inputFormat

The first line contains two integers m and q (1 ≤ m, q ≤ 10⁵), where m is the number of gems initially and q is the number of operations.

The second line contains m space-separated integers \(v_1, v_2, \ldots, v_m\) (1 ≤ \(v_i\) ≤ 10⁹), representing the precious values of the gems.

Each of the next q lines represents an operation in one of the following two formats:

• 1 n: Query for the nth most precious gem.
• 2 x: Add a gem with value x to the system.

outputFormat

For every query operation of the format 1 n, output the value of the nth most precious gem in a separate line.

sample

5 5
10 20 30 40 50
1 1
2 35
1 3
2 60
1 5

50
35
30