Dynamic Simple Polygon Queries

Alice gives Bob a simple N-sided polygon on the plane. A simple N-polygon is defined by N distinct vertices and the line segments connecting consecutive vertices, with the 1^st vertex and the N^th vertex also connected.

The edges of the polygon (i.e. the line segments) may only intersect at their common endpoints. Sometimes, Alice points to a location in the plane and asks Bob: "Is this point inside the polygon, outside the polygon, or on its boundary?" Here, if the point coincides with one of the vertices or lies on one of the edges, it is considered to be on the boundary of the polygon.

To increase the difficulty, Alice may also modify the polygon. A modification command is given as a 6-tuple \[ \langle x_a, y_a, x_b, y_b, x_c, y_c \rangle \] which means that the edge connecting the point \((x_a, y_a)\) and \((x_b, y_b)\) is removed, and a new vertex \((x_c, y_c)\) is inserted (the new vertex is guaranteed not to coincide with any existing vertex and is not on any current edge). Then, two new edges from \((x_a, y_a)\) to \((x_c, y_c)\) and from \((x_c, y_c)\) to \((x_b, y_b)\) are added, resulting in a new simple polygon.

Bob’s task is to correctly answer each of Alice’s queries. However, each query is generated from the answer to the previous query. Specifically, every query comes with 7 non-negative integers:

\(r,\; x_{in},\; y_{in},\; x_{out},\; y_{out},\; x_{bd},\; y_{bd}\)

and the actual query point \((X,Y)\) is determined by the previous query point \((x_0,y_0)\) (for the very first query, assume \(x_0=y_0=0\)) and the previous answer as follows:

For example, if the previous query point was outside the polygon then

\[ X = (r\times x_0 + x_{out})\bmod 10^9, \quad Y = (r\times y_0 + y_{out})\bmod 10^9 \]

You should assume that when the previous answer is INSIDE or BOUNDARY, the query point \((X,Y)\) is computed similarly using \(x_{in}, y_{in}\) or \(x_{bd}, y_{bd}\) respectively.

The input begins with the initial polygon, followed by a sequence of operations. Each operation is one of the following:

• Query operation (7 integers): Use the above formulas to compute the query point and output one of INSIDE, OUTSIDE, or BOUNDARY based on the location of the point relative to the current polygon.
• Modification operation (6 integers): Remove the edge connecting the vertices with coordinates \((x_a,y_a)\) and \((x_b,y_b)\) (these vertices are guaranteed to be adjacent in the polygon) and insert a new vertex \((x_c,y_c)\) between them.

Input Format: The input is given as follows:

N
x1 y1
x2 y2
...
xN yN
M
op1
op2
...
opM

Each operation op is a line containing either 7 integers (query operation) or 6 integers (modification operation). It is guaranteed that all coordinates (including those in queries) are non-negative integers less than \(10^9\), and in the polygon (excluding query points) no two vertices share the same x or y coordinate.

Output Format: For each query operation, output a line containing one of the strings INSIDE, OUTSIDE, or BOUNDARY.

inputFormat

The input begins with an integer N (the number of vertices of the initial polygon). The next N lines each contain two integers, representing the coordinates of the polygon vertices in order (either clockwise or counterclockwise). Following that is an integer M denoting the number of operations. Each of the next M lines represents an operation. An operation containing 7 integers is a query operation (with integers r, xin, yin, xout, yout, xbd, ybd), and an operation containing 6 integers is a modification operation (with integers xa, ya, xb, yb, xc, yc).

Note that for query operations, the actual query point \((X,Y)\) is computed based on the previous query's point \((x_0,y_0)\) (with \((0,0)\) for the first query) and the previous answer as described in the problem statement.

outputFormat

For each query operation, output a single line containing one of the strings: INSIDE, OUTSIDE, or BOUNDARY, indicating the position of the query point relative to the current polygon.

sample

4
1 1
5 1
5 5
1 5
3
1 10 10 2 2 100 100
5 1 5 5 6 3
2 3 3 10 10 0 0

INSIDE
OUTSIDE

</p>