Migrated from Lutece 3135 末日下的恋歌Ⅱ

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Tag：李超线段树

众所周知，在UESTC_暑假前集训中，出现脏翅膀要素的题目有很多。

因此，在这次的2024 UESTC ICPC Training for Data Structures中，将会继续延续这一传统。

凯伊姆在摆平了诺瓦斯·艾蒂尔上发生的一切后，在梦中聆听到了所谓神明的呓语，神明请求凯伊姆为其解决如下的问题：

• 在平面上新增一条线段，记第 $i$ 条被加入的线段编号为 $i$ 。
• 给定一个数 $k$ ，询问在所有已经加入的线段中，与直线 $x=k$ 相交，且交点的纵坐标最大的线段的编号。

如果凯伊姆能正确解答神明的问题的话，说不定会有什么可以被称之为奇迹的事物将会发生吧……

Input

输入的第一行包括一个正整数 $n$ ，代表操作的个数。

在接下来的 $n$ 行中，每行有若干个由空格分隔开的整数，每行的第一个整数为 $tp$ ，代表该次操作的类型。

• 若 $tp=0$ ，则后跟一个整数 $k$ ，代表本次操作为查询所所有与直线 $x=(k+lstans-1)\bmod 39989+1$ 相交的线段中，交点纵坐标最大的线段编号。
• 若 $tp=1$ ，则后跟四个整数 $x_1,y_1,x_2,y_2$ ，记 $x'_i=(x_i+lstans-1)\bmod 39989+1,y'_i=(y_i+lstans-1)\bmod 10^9+1$ 。本次操作为插入一条两端点分别为 $(x_1',y_1'),(x_2',y_2')$ 的线段。

其中 $lstans$ 为上一次询问的答案，初始时， $lstans=0$ 。

Output

对于每个 $tp=0$ 的操作，输出一行一个整数，代表交点纵坐标最大的线段的编号。

若不存在任何一条线段与查询直线有交，则输出 $0$ 。

若有多条线段与查询直线的交点纵坐标都是最大的，则输出这些线段中编号的最小值。

注意在每次操作后 $lstans$ 的值都要进行更新。

Samples

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

Constraints

$1\le n\le 1\times 10^5,1\le k,x_1,x_2\le 39989,1\le y_1,y_2\le 10^9$

数据不保证 $x_1'\ne x_2'$ ，对于一条 $x_1'= x_2'$ 的线段，认为其与直线 $x=x_1'$ 的交点为其两端点中纵坐标较大的端点。

Note

样例解释如下：

初始时， $lstans$ 的值为 $0$ 。

对于第一次操作，解密后得到1 8 5 10 8。

对于第二次操作，解密后得到1 6 7 2 6。

对于第三次操作，解密后得到0 2，此时 $lstans$ 被更新为$2$。

对于第四次操作，解密后得到0 11，此时 $lstans$ 被更新为$0$。

对于第五次操作，解密后得到1 4 7 6 7。

对于第六次操作，解密后得到0 5。

Bonus：

在往年的UESTC_暑假前集训中，出现脏翅膀要素的题目有（但不限于）：

• 2023 UESTC ICPC Training for Graph中，T题。
• 2021 UESTC ICPC Training for Math and Geometry中，A题、B题、C题、D题、E题和F题。
• 2020 UESTC ICPC Training for Data Structures中，Lutece2374   尤斯蒂娅的麦穗
• Lutece
题。

Resources

2024 UESTC ICPC Training for Data Structures