U521685 [SDOI2014] 里面还是外面

- 数据更新：现在选取了原题的总共 10 个测试点，并删除了其中两个不符合题意的。

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 的每一次修改命令可以看作是一个六元组：$\langle x_a,y_a,x_b,y_b,x_c,y_c\rangle$ 表示删除了坐标位置 $(x_a,y_a)$，与坐标位置 $(x_b,y_b)$ 的点之间的连边，并插入新的点 $(x_c,y_c)$。 这里我们保证坐标为 $(x_a,y_a)$ 的点与坐标为 $(x_b,y_b)$ 的点总是存在的。因为 Alice 保证了所有出现的点（这包括了询问点）的坐标都是非负整数，且都小于 $10^9$，且多边形中（这不包括询问点）任意两个点的 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 \cdot x_0 + x_{out}) \bmod 10^9,Y = (r \cdot y_0 + y_{out}) \bmod 10^9$ 对于第一次讯问，我们假设 $x_0 = y_0 = 0$，也就是说将 $(0,0)$ 考虑为前一次的询问。

输入文件的第一行有一个整数 $N$，表示初始时多边形的点数。 之后 $N$ 行，每行一对非负整数 $x$ 和 $y$ $(0\le x,y

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

对于 $100%$ 的数据：$N\le 5\cdot 10^4,Q\le 5\cdot 10^4$，所有坐标非负且均小于 $10^9$，而 $r$ 或者为 $1$ 或者为 $0$。