Description

Alice gives a simple $N$-gon on the plane. A simple $N$-gon consists of $N$ given endpoints and straight segments connecting adjacent points. In particular, we consider vertex $1$ adjacent to vertex $N$.

For distinct boundary segments, they only intersect at common endpoints. Sometimes Alice points to a point in the plane and asks Bob: “Is this point inside the polygon, outside the polygon, or on the boundary?”

At that time, if the pointed point is a vertex of the polygon or lies on any edge of the polygon, it is considered to be on the boundary. Sometimes, to increase the difficulty, Alice deletes the edge connecting $a$ and $b$, inserts a new point $c$ (the newly inserted point is guaranteed not to coincide with any existing endpoint and not to lie on any existing edge), and then adds edges from $a$ to $c$ and from $b$ to $c$, thereby obtaining a new simple polygon.

Alice guarantees that the figure obtained by such an operation is always a simple polygon. What Bob has to do is answer Alice’s questions correctly. In fact, each of Alice’s questions will be determined by Bob’s previous answer: although this answer is unique, it implies that if Bob cannot answer the previous question, he cannot get Alice’s next question.

However, Alice’s modifications are indeed prepared in advance. In detail: each modification command by Alice can be viewed as a 6-tuple $\langle x_a, y_a, x_b, y_b, x_c, y_c \rangle$, which means the edge between $(x_a, y_a)$ and $(x_b, y_b)$ is deleted, and a new point $(x_c, y_c)$ is inserted.

We guarantee that the points at coordinates $(x_a, y_a)$ and $(x_b, y_b)$ always exist. Because Alice guarantees that all appearing points (this includes query points) have non-negative integer coordinates, all less than $10^9$, and among the polygon’s points (this does not include query points) any two points have distinct $x$-coordinates and also distinct $y$-coordinates. Therefore, for each query Alice will give 7 non-negative integers: $r$, $x_{\text{in}}$, $y_{\text{in}}$, $x_{\text{out}}$, $y_{\text{out}}$, $x_{\text{bd}}$, $y_{\text{bd}}$. The actual query point $(X, Y)$ for this query is determined by the previous query point $(x_0, y_0)$ and the previous answer. For example, if the previous query point was outside the polygon, then:

For the first query, assume $x_0 = y_0 = 0$, i.e., treat $(0, 0)$ as the previous query.

Similarly, if the previous point was inside, replace $x_{\text{out}}, y_{\text{out}}$ with $x_{\text{in}}, y_{\text{in}}$; if it was on the boundary, use $x_{\text{bd}}, y_{\text{bd}}$.

Input Format

The first line contains an integer $N$, the number of vertices of the initial polygon.

Then follow $N$ lines, each with a pair of non-negative integers $x$ and $y$ ($0 \leq x, y < 10^9$). They describe all vertices of the polygon in some order and are indexed from $1$ to $N$. Here we only assume that the point $(10^{100}, 10^{100})$ in the plane is certainly outside the polygon. The next line contains an integer $Q$, the total number of operations.

Each of the next $Q$ lines starts with a number $p$. If $p = 0$, it is a query; if $p = 1$, it is a modification.

• For a query, the next 7 non-negative integers are: $r$, $x_{\text{in}}$, $y_{\text{in}}$, $x_{\text{out}}$, $y_{\text{out}}$, $x_{\text{bd}}$, $y_{\text{bd}}$.
• For a modification, the next 6 integers are: $x_a$, $y_a$, $x_b$, $y_b$, $x_c$, $y_c$.

Output Format

For each query operation, output a single line containing exactly one string: either in, out, or bd (all lowercase), indicating that the query point is inside the polygon, outside the polygon, or on the boundary, respectively.

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

Hint

For 100% of the testdata: $N \leq 50000$, $Q \leq 50000$, all coordinates are non-negative and less than $10^9$, and $r$ is either $1$ or $0$.

Translated by ChatGPT 5