## Maintaining an Envelope

Points: 30
Time limit: 3.0s
Memory limit: 1G

Problem types

There is a 2D-plane where only lattice points with their x-coordinates from $$1$$ to $$N$$ are of interest.

Support the following operations:

• 1 n m b Add a line with an ID of $$n$$ $$(1 \leq n \leq Q)$$ in the form of $$y = mx + b$$ to the plane. All line IDs are guaranteed to be distinct.
• 2 n Delete the line with an ID of $$n$$. It is guaranteed that the line exists at this time.
• 3 c Output the ID of the line that gives the minimum value at $$x = c$$ $$(c \in \mathbb{Z}, 1 \leq c \leq N)$$. If multiple lines give the minimum value, output the ID of the line with a lower ID. It is guaranteed that there is least one line on the plane at this time.

You will be asked to support these operations a total of $$Q$$ times.

#### Constraints

• $$1 \leq Q \leq 2 \cdot 10^5$$
• $$1 \leq N \leq 10^9$$
• $$0 \leq |m|, |b| \leq 10^8$$

#### Input Specification

The first line of input will contain two numbers: $$N$$ and $$Q$$.

The next $$Q$$ lines each contain an operation, as described above.

#### Output Specification

For each of the 3 c operation, output one line: the answer, as described above.

#### Sample Input

100 8
1 3 -10 2
1 1 -9 6
1 2 -4 4
1 4 1 1
3 39
2 4
2 3
3 40

#### Sample Output

3
1