#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## 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 *D _{i}* dollars. It is guaranteed that no two

*D*will be the same. He then has to process

_{i}*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 *i*th integer representing *D _{i}*.

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 ≤ D_{i}, x ≤ 10^{9}.

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

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 13 | 20 | 1s | 256MB | Minimum |

2 | 19 | 20 | 1s | 256MB | Minimum |

3 | 22 | 20 | 1s | 256MB | Minimum |

4 | 46 | 80 | 1s | 256MB | Minimum |

5 | 0 | 1 | 1s | 256MB | Minimum |

### Judge Compile Command

g++ ans.cpp -o redpacket -Wall -static -O2 -lm -m64 -s -w -std=gnu++14 -fmax-errors=512