P3316 [SDOI2014] 里面还是外面

upd： - 数据更新：现在选取了原题的总共 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_{\text{in}}$，$y_{\text{in}}$，$x_{\text{out}}$，$y_{\text{out}}$，$x_{\text{bd}}$，$y_{\text{bd}}$。而 Alice 这一次询问真正要询问的点 $(X, Y)$ 的坐标将由上一次询问的点 $(x_0, y_0)$ 与上一次询问的回答而决定。例如，若上一次询问的点在多边形外，则： $$ X = (r \times x_0 + x_{\text{out}}) \bmod 10^9 $$ $$ Y = (r \times y_0 + y_{\text{out}}) \bmod 10^9 $$ 对于第一次询问，我们假设 $x_0 = y_0 = 0$，也就是说将 $(0,0)$ 考虑为前一次的询问。

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

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

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