[Heoi2013]Segment

时间限制:40s      空间限制:256MB

题目描述

要求在平面直角坐标系下维护两个操作:
1.在平面上加入一条线段。记第i条被插入的线段的标号为i。
2.给定一个数k,询问与直线 x = k相交的线段中,交点最靠上的线段的编号。  


输入格式

 
第一行一个整数n,表示共n 个操作。
接下来n行,每行第一个数为0或1。
 
若该数为 0,则后面跟着一个正整数 k,表示询问与直线 
x = ((k +lastans–1)%39989+1)相交的线段中交点(包括在端点相交的情形)最靠上的线段的编号,其中%表示取余。若某条线段为直线的一部分,则视作直线与线段交于该线段y坐标最大处。若有多条线段符合要求,输出编号最小的线段的编号。
若该数为 1,则后面跟着四个正整数 x0, y0, x 1, y 1,表示插入一条两个端点为
((x0+lastans-1)%39989+1,(y0+lastans-1)%10^9+1)和((x
1+lastans-1)%39989+1,(y1+lastans-1)%10^9+1) 的线段。
其中lastans为上一次询问的答案。初始时lastans=0。 
 
 


输出格式

对于每个 0操作,输出一行,包含一个正整数,表示交点最靠上的线段的编号。若不存在与直线相交的线段,答案为0。


样例输入

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 
 
 

提示

对于100%的数据,1 ≤ n ≤ 10^5 , 1 ≤  k, x0, x1 ≤ 39989, 1 ≤ y0 ≤ y1 ≤ 10^9。


题目来源

没有写明来源

Menuappsclose