Description

Maintain two operations in the 2D Cartesian coordinate system:

1. Insert a line segment into the plane. The index of the i-th inserted segment is $i$.
2. Given a number $k$, query among all segments that intersect the line $x = k$, and return the index of the segment whose intersection point has the largest $y$-coordinate.

Input Format

This problem enforces online input.

The first line contains an integer $n$, the number of operations.

Then $n$ lines follow. On each line there are several integers separated by spaces. On the $(i + 1)$-th line, the first integer is $op$, indicating the type of the $i$-th operation.

• If $op = 0$, then it is followed by an integer $k$. This operation queries among all segments that intersect the line $x = (k + lastans - 1) \bmod 39989 + 1$, and returns the index of the segment whose intersection point has the largest $y$-coordinate.
• If $op = 1$, then it is followed by four integers $x_0, y_0, x_1, y_1$. Define $x_i' = (x_i + lastans - 1) \bmod 39989 + 1$, $y_i' = (y_i + lastans - 1) \bmod 10^9 + 1$. This operation inserts a segment with endpoints $(x_0', y_0')$ and $(x_1', y_1')$.

Here $lastans$ is the answer to the previous query. Initially, $lastans = 0$.

Output Format

For each query, output one line containing a single integer: the index of the segment whose intersection point has the largest $y$-coordinate. If no segment intersects the query line, output $0$. If multiple segments have the same maximum intersection $y$-coordinate, output the smallest index among them, and $lastans$ should also be updated to this smallest index.

6 
1 8 5 10 8 
1 6 7 2 6 
0 2 
0 9 
1 4 7 6 7 
0 5

2 
0 
3

Hint

Explanation for Sample $1$

For the first operation, after decoding it becomes 1 8 5 10 8.

For the second operation, after decoding it becomes 1 6 7 2 6.

For the third operation, after decoding it becomes 0 2, and $lastans$ is updated to $2$.

For the fourth operation, after decoding it becomes 0 11, and $lastans$ is updated to $0$.

For the fifth operation, after decoding it becomes 1 4 7 6 7.

For the sixth operation, after decoding it becomes 0 5.

Constraints

For $30\%$ of the testdata, $n \leq 10^3$ is guaranteed.

For $100\%$ of the testdata, it is guaranteed that $1 \leq n \leq 10^5$, $1 \leq k, x_0, x_1 \leq 39989$, $1 \leq y_0, y_1 \leq 10^9$.

Notes

It is not guaranteed that $x_0 \neq x_1$. For a segment with $x_0' = x_1'$, its intersection with $x = x_0'$ is defined to be the endpoint with the larger $y$-coordinate.

Translated by ChatGPT 5