Problem Description
Jianzhi has been packing red packets. To decide on what notes to put in each of the red packets, he has again decided to use his bot, which greedily selects the most valuable note that does not exceed the value he is trying to make, and repeats this process until he achieves his target value.
Jianzhi starts off with N types of notes, with note i having a value of Di dollars. It is guaranteed that no two Di will be the same. He then has to process Q queries.
Each query can be of the form:
- 1 x, which adds a new denomination of value x into Jianzhi's set. It is guaranteed that no such denomination already exists in his set.
- 2 x, which removes a denomination of value x from Jianzhi's set. It is guaranteed that Jianzhi has such a denomination in his set.
- 3 x, which queries how many notes Jianzhi needs to make x dollars, with his bot's algorithm.
Input
The first line of input will contain two integers, N and Q.
The second line of input will contain N integers, with the ith integer representing Di.
The next Q lines of input will contain one query each, in the form stated above.
Output
The output should contain one line for each query of type 3, answering the query. If Jianzhi cannot make the value with his algorithm, output -1 on that line instead.
Limits
For all subtasks: 1 ≤ Di, x ≤ 109.
Subtask 1 (13%): 1 ≤ N, Q ≤ 1000.
Subtask 2 (19%): 1 ≤ N, Q ≤ 300000. There will only be queries of type 3.
Subtask 3 (22%): 1 ≤ N, Q ≤ 300000. There will only be queries of type 1 or 3.
Subtask 4 (46%): 1 ≤ N, Q ≤ 300000.
Subtask 5 (0%): Sample Testcases.
Sample Input 1
Input
3 6
2 3 5
3 8
3 9
1 6
3 9
2 2
3 4
Output
2
-1
2
-1