Alice has provided a simple $N$-polygon on a plane. A simple $N$-polygon consists of $N$ given vertices and line segments connecting adjacent vertices. Specifically, we consider vertex $1$ and vertex $N$ to be adjacent. For any two distinct line segments on the boundary, we guarantee that they only intersect at their common endpoints.
Sometimes, Alice points to a location on the plane and asks Bob: "Is this point inside the polygon, outside the polygon, or on the boundary?"
If the point she points to is a vertex of the polygon or lies on one of the polygon's edges, it is considered to be on the boundary of the polygon.
At other times, to increase the difficulty, Alice will remove the edge connecting $a$ and $b$, and insert a new point $c$ (the newly inserted point is guaranteed not to coincide with any existing vertex and not to lie on any existing boundary), then add edges from $a$ to $c$ and from $b$ to $c$, thereby obtaining a new simple polygon.
Alice guarantees that the new shape obtained by such an operation is always a simple polygon.
Bob's task is to answer Alice's questions accurately. In reality, each of Alice's questions is determined by Bob's previous answer. Although this answer is unique, it means that if Bob cannot answer the previous question, he cannot receive Alice's next question. However, Alice's modifications to the polygon are prepared in advance.
Specifically, each of Alice's modification commands can be viewed as a 6-tuple: $\langle x_a, y_a, x_b, y_b, x_c, y_c \rangle$ This represents removing the edge between the coordinate position $(x_a, y_a)$ and the coordinate position $(x_b, y_b)$, and inserting a new point $(x_c, y_c)$. Here, we guarantee that the points at coordinates $(x_a, y_a)$ and $(x_b, y_b)$ always exist.
Because Alice guarantees that the coordinates of all points that appear (including query points) are non-negative integers less than $1\,000\,000\,000$, and that any two points in the polygon (excluding query points) have different $x$-coordinates and different $y$-coordinates.
Therefore, for each query, Alice will provide 7 non-negative integers: $r, x_{in}, y_{in}, x_{out}, y_{out}, x_{bd}, y_{bd}$
The coordinates $(X, Y)$ of the point Alice is actually asking about in this query are determined by the point $(x_0, y_0)$ from the previous query and the answer to that previous query. For example, if the point from the previous query was outside the polygon, then: $X = (r \cdot x_0 + x_{out}) \pmod{1\,000\,000\,000}$ $Y = (r \cdot y_0 + y_{out}) \pmod{1\,000\,000\,000}$
For the first query, we assume $x_0 = y_0 = 0$.
Input
The first line of the input file contains an integer $N$, representing the number of vertices of the initial polygon.
Following this are $N$ lines, each containing a pair of non-negative integers $x$ and $y$ ($0 \le x, y < 1\,000\,000\,000$). These describe the coordinates of all vertices of the polygon in a certain order, numbered $1$ to $N$.
Here, we only consider that for any point $(10^{100}, 10^{100})$ on the plane, it is definitely outside the polygon.
The next line contains an integer $Q$, representing the total number of operations.
Following this are $Q$ lines, each starting with an integer $p$. If $p=0$, it represents a query; if $p=1$, it represents a modification.
For a query, 7 non-negative integers follow: $r, x_{in}, y_{in}, x_{out}, y_{out}, x_{bd}, y_{bd}$
For a modification, 6 integers follow: $x_a, y_a, x_b, y_b, x_c, y_c$
Output
For each query operation, output a single line containing only one string, which is either in, out, or bd (all lowercase), representing whether the query point is inside, outside, or on the boundary of the polygon, respectively.
Examples
Input 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
Output 1
out out in in out out out in
Constraints
- For 10% of the data: $N \le 1000$, $Q \le 5000$.
- For 10% of the data: $N \le 1000$, $Q \le 50000$, no modification operations.
- For 20% of the data: $N \le 50000$, $Q \le 50000$, no modification operations.
- For 10% of the data: $N \le 50000$, $Q \le 50000$, the coefficient $r$ for every query operation is always $0$.
- For 20% of the data: $N \le 50000$, $Q \le 50000$, in every modification operation, the $x$-coordinate of $c$ differs from the $x$-coordinate of $a$ by at most $1$, or differs from the $x$-coordinate of $b$ by at most $1$.
- For 100% of the data: $N \le 50000$, $Q \le 50000$, all coordinates are non-negative and less than $1\,000\,000\,000$, and $r$ is either $1$ or $0$.