[SDOI2014] 里面还是外面

题目描述

Alice给出了平面上的一个简单N-多边形。所谓简单N-多边形,包括N个给定的端点,和连接相邻点的直线段,特别的,我们认为1号点与N号是相邻的。 对于边界上不同的直线段,保证它们只会在公共端点处相交。有的时候Alice会指着平面上一个点,然后问Bob:”这个点是在多边形的里面呢,还是外面呢,还是在边界上呢?“ 这个时候,如果她所指的点是多边形的一个顶点或者在多边形某条边的边界上,都将被认为是在多边形的边界上。还有的时候,Alice为了加大难度,会删除连接a和b的边,并插入新的点c(新插入的点保证不与任何已有的端点重合,也不在任何边界上),然后新增a到c的边与b到c的边,从而得到一个新的简单多边形。 Alice保证这样的操作得到的新图形总是简单多边形。Bob要做的,就是准确回答出Alice的提问。而实际上,Alice的每一次提问都将由Bob上一次的回答决定,虽然这个回答是唯一的,但却意味着如果Bob不能回答出前一个问题,就不能拿到Alice的下一个问题。 不过,Alice对多边形的修改确实事先准备好的。详细来说:Alice的每一次修改命令可以看作是一个六元组:〈x\_a,y\_a,x\_b,y\_b,x\_c,y\_c〉表示删除了坐标位置(x\_a,y\_a),与坐标位置(x\_b,y\_b)的点之间的连边,并插入新的点(x\_c,y\_c)。 这里我们保证坐标为(x\_a,y\_a)的点与坐标为(x\_b,y\_b)的点总是存在的。因为Alice保证了所有出现的点(这包括了询问点)的坐标都是非负整数,且都小于1000000000,且多边形中(这不包括询问点)任意两个点的x坐标不同,y坐标也不同。所以每一次询问Alice将给出7个非负整数:r,x\_{in},y\_{in},x\_{out},y\_{out},x\_{bd},y\_{bd}而Alice这一次询问真正要询问的点(X,Y)的坐标将由上一次询问的点(x\_0,y\_0)与上一次询问的回答而决定。例如,若上一次询问的点在多边形外,则:X = (r \* x\_0 + x\_{out}) mod 1000000000Y = (r \* y\_0 + y\_{out}) mod 1000000000对于第一次讯问,我们假设x\_0 = y\_0 = 0,也就是说将(0,0)考虑为前一次的询问。

输入输出格式

输入格式


输入文件的第一行有一个整数N,表示初始时多边形的点数。 之后N行,每行一对非负整数x和y(0<=x,y<1000000000)。按照某一顺序依次描述了多边形的所有顶点的坐标,并编号为1到N。这里我们只认为,对于平面上的一点(10^100,10^100)一定是处在多边形以外的。之后一行有一个整数Q,表示总的操作次数。 之后Q行,每行第一个数字p,如果p=0,则表示询问;如果p=1,则表示修改。 - 对于询问,之后给出了7个非负整数,它们是:r,x\_{in},y\_{in},x\_{out},y\_{out},x\_{bd},y\_{bd} - 对于修改,之后给出了6个整数,它们是:x\_a,y\_a,x\_b,y\_b,x\_c,y\_c

输出格式


对于每一次询问操作,单独输出一行且只包含一个字符串,它或者是in、或者是out、或者是bd(均为小写字符),分别表示询问点在多边形的内、外或边界。

输入输出样例

输入样例 #1

6
249999999 499999998
583333331 83333333
83333333 333333332
333333332 999999996
833333330 749999997
499999998 833333330
12
0 1 872826049 679758020 472526437 270998755 15447952 502239247
1 833333330 749999997 499999998 833333330 916666663 666666664
1 833333330 749999997 916666663 666666664 416666665 916666663
0 1 371653715 747730364 409617871 21996163 118531999 759280767
1 249999999 499999998 583333331 83333333 666666664 166666666
0 1 195920917 488293591 322952040 262793733 678458193 506876149
0 1 203963007 782710007 391614158 831643205 340800821 896322422
0 1 498571077 461554269 765704840 973009111 152064733 114249255
1 499999998 833333330 249999999 499999998 999999996 583333331
0 1 159294077 702544938 787871788 619972292 941209243 950700951
0 1 791254252 411705638 382076333 263993056 306662346 47793905
0 1 13359599 513224793 415037020 28305143 48117026 34994422

输出样例 #1

out
out
in
in
out
out
out
in

说明

对于100%的数据:N<=50000,Q<=50000,所有坐标非负且均小于1000000000,而r或者为1或者为0。