Jewel Management

This problem involves managing a collection of jewels. Initially, you are given N types of jewels with their corresponding values and then Q events occur. There are two types of events:

• Type 1: "1 i M" means that M jewels of type i are added to the collection. The value of a jewel of type i is given by \(v_i\) (where \(1 \leq i \leq N\)).
• Type 2: "2" represents a customer request. The system should output the value of the most valuable jewel available. If no jewel is available, output -1.

The operations on the collection must be handled using a max-heap (priority queue) data structure with lazy deletion. That is, when a jewel is removed upon a customer request, if there are remaining jewels of the same type then the jewel should still be available for future requests.

Note: All formulas are written in \(\LaTeX\) format. For example, the number of jewel types is denoted by \(N\) and the number of events by \(Q\).

inputFormat

The input is given from standard input and has the following format:

N Q
v1 v2 ... vN
[event_1]
[event_2]
...
[event_Q]

Here, the first line contains two integers \(N\) and \(Q\). The second line contains \(N\) integers, where the \(i\)-th integer represents the value \(v_i\) of the jewel type \(i\). Each of the next \(Q\) lines describes an event. An event is either of the form "1 i M" (to add \(M\) jewels of type \(i\)) or "2" (a customer request to get the most valuable jewel).

outputFormat

For each event of type 2, output the value of the most valuable jewel available after considering all previous events. If there is no available jewel, output -1. Each answer should be printed on a new line, using standard output.

## sample

3 6
4 5 3
1 1 2
1 2 3
2
2
1 2 1
2

5
5
5

</p>