Shark and Small Fish

In a lake, there are \(n\) small fish. The weight of the \(i\)-th fish is \(w_i\). There are \(q\) operations, each of which is one of the following three types:

• 1 s k: A big shark with initial weight \(s\) arrives with a goal to reach at least weight \(k\) (i.e. \(\ge k\)). The shark can eat a small fish with weight \(w\) if its current weight is strictly greater than \(w\). After eating a fish, its weight increases by \(w\). Determine the minimum number of small fish the shark needs to eat to achieve its goal. If it is impossible, output -1.
• 2 w: Add a small fish with weight \(w\) into the lake.
• 3 w: Delete one small fish with weight \(w\) from the lake. It is guaranteed that at least one such fish exists.

Note that the fish in the lake are maintained dynamically. For each query of type 1, the simulation of the shark eating small fish does not affect the lake.

inputFormat

The first line contains two integers \(n\) and \(q\) — the initial number of small fish and the number of operations.

The second line contains \(n\) integers \(w_1, w_2, \dots, w_n\), representing the weights of the fish.

The following \(q\) lines each describe an operation in one of the following formats:

• 1 s k
• 2 w
• 3 w

outputFormat

For each operation of type 1, output a single integer on a new line — the minimum number of small fish the shark needs to eat to reach at least weight \(k\), or -1 if it is impossible.

sample

3 4
2 3 5
1 4 15
2 1
1 10 20
1 1 2

-1
3
-1