题目背景

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_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（均为小写字符），分别表示询问点在多边形的内、外或边界。

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

out
out
in
in
out
out
out
in

提示

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