## Maintaining an Envelope

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
```

## Comments