This is an interactive problem.

Given $n$ points on a plane, where the $(i+1)$-th point is $(x_i, y_i)$ with an initial value $d_i$, for $0 \le i < n$.

You need to perform $m$ operations in sequence, all of which are known from the beginning.

The $(j+1)$-th operation provides three numbers $a_j, b_j, c_j$, and an operation $o_j$, representing the half-plane $a_jx + b_jy < c_j$, for $0 \le j < m$.

You must execute the following steps in order:

First, set $s_j = \epsilon_D$. Then, for every $i$ such that $a_jx_i + b_jy_i < c_j$, first update $s_j$ to $s_j + d_i$, and then update $d_i$ to $o_j \cdot d_i$.

After completing these modifications, you obtain the answer $s_j$ for this operation.

Here, $d_i$ belongs to an abstract data type $D$, and $o_j$ belongs to an abstract data type $O$.

An abstract operation $+: D \times D \to D$ is defined on $D$. An abstract operation $\cdot: O \times D \to D$ is defined on $D$ and $O$. An abstract operation $\cdot: O \times O \to O$ is defined on $O$.

$\epsilon_D$ is a special element in $D$ called the identity element. $\epsilon_O$ is a special element in $O$ called the identity element.

These operations satisfy the following properties:

For any $a, b, c \in D$, $a + b = b + a$, $(a + b) + c = a + (b + c)$, and $a + \epsilon_D = \epsilon_D + a = a$.

For any $u, v, w \in O$, $(u \cdot v) \cdot w = u \cdot (v \cdot w)$ and $u \cdot \epsilon_O = \epsilon_O \cdot u = u$.

For any $u, v \in O$ and $a, b \in D$, $(u \cdot v) \cdot a = u \cdot (v \cdot a)$, $u \cdot (a + b) = (u \cdot a) + (u \cdot b)$, $\epsilon_O \cdot a = a$, and $u \cdot \epsilon_D = \epsilon_D$.

Executing each $+$ or $\cdot$ operation incurs a certain cost. Specifically, when calculating $a + b$ or $a \cdot b$, if both $a$ and $b$ are not $\epsilon_D$ or $\epsilon_O$, the cost is 1; otherwise, the cost is 0. You must ensure that every answer is correct and that the total cost does not exceed the cost limit of the current subtask.

Input

The interactive library reads input data in the following format:

• First line: $n$
• Next $n$ lines: $x_i \; y_i \; d_i$ ($d_i$ is represented by two integers)
• $(n+2)$-th line: $m$
• Next $m$ lines: $a_i \; b_i \; c_i \; o_i$ ($o_i$ is represented by 4 integers)

Elements in $D$ are $2 \times 1$ matrices, and elements in $O$ are $2 \times 2$ matrices. The elements in the matrices are integers modulo $2^{32}$.

$+$ corresponds to matrix addition, and $\cdot$ corresponds to matrix multiplication. Please refer to the provided interactive library implementation for details.

In the actual evaluation environment, the input/output format and the definitions of $D$ and $O$ may differ.

Output

The interactive library prints your answers in the following format:

• First $m$ lines: $s_i$, represented by two integers
• $(m+1)$-th line: Total cost

Implementation Details

You must include the header file hpmq.h.

The header file defines the data types Data ($D$) and Operation ($O$). You can use the following defined member functions to manipulate data of type Data and Operation:

void Data::add_eq(const Data &a)

w.add(a) calculates $w + a$ and stores the result in $w$. The cost of each call is 1 if both $w$ and $a$ are not the identity element, and 0 otherwise.

void Data::add(const Data &a,const Data &b)

w.add(a, b) calculates $a + b$ and stores the result in $w$. The cost of each call is 1 if both $a$ and $b$ are not the identity element, and 0 otherwise.

void Data::clr()

w.clr() stores $\epsilon_D$ in $w$. The cost of each call is 0.

void Data::print()const

w.print() outputs $w$ as the answer for an operation. The cost of each call is 0. This function must be called exactly $m$ times, corresponding to the answers for each operation in order.

bool Data::empty()const

w.empty() checks if $w$ is $\epsilon_D$. It returns true if it is, and false otherwise. The cost of each call is 0.

void Operation::apply(Data &a)const

w.apply(a) calculates $w \cdot a$ and stores the result in $a$. The cost of each call is 1 if both $w$ and $a$ are not the identity element, and 0 otherwise.

void Operation::apply(Operation &u)const

w.apply(u) calculates $w \cdot u$ and stores the result in $u$. The cost of each call is 1 if both $w$ and $u$ are not the identity element, and 0 otherwise.

void Operation::clr()

w.clr() stores $\epsilon_O$ in $w$. The cost of each call is 0.

bool Operation::empty()const

w.empty() checks if $w$ is $\epsilon_O$. It returns true if it is, and false otherwise. The cost of each call is 0.

Additionally, you can use assignment operators, copy constructors, or default constructors for Data or Operation types. Taking Data as an example:

w = u copies $u$ into $w$. The cost of each call is 0.

Data w(u); or Data w = u; creates a new $w$ as a copy of $u$. The cost of each call is 0.

Data w; creates a new $w$ initialized to $\epsilon_D$. The cost is 0.

Operation w; creates a new $w$ initialized to $\epsilon_O$. The cost is 0.

Except for the operations described above, other operations may be considered an attack on the evaluation system.

sizeof(Data) and sizeof(Operation) do not exceed 64. Furthermore, the interactive library requires no more than 64MB of memory. Time and memory limits include the time and memory used by the interactive library. A correct program can be written using only assignment, constructors, apply, and add; other functions may provide convenience.

You must implement the following function:

void solve(
    const int n,
    const int m,
    const int *x,
    const int *y,
    const Data *d,
    const int *a,
    const int *b,
    const int *c,
    const Operation *o)

• $n$: Number of points.
• $x, y, d$: Arrays of size $n$, where $(x_i, y_i)$ are the coordinates of the $(i+1)$-th point, and $d_i$ is its initial value.
• $m$: Number of operations.
• $a, b, c, o$: Arrays of size $m$, where the $(i+1)$-th operation range is the half-plane $a_ix + b_iy < c_i$, and the modification operation is $o_i$.

Constraints

For all data, the following holds:

$|x_i| \le 10^6$, $|y_i| \le 10^6$.

$|a_i| \le 10^3$, $|b_i| \le 10^3$, $b_i \ne 0$, $|c_i| \le 10^6$.

$x_i, y_i, a_i, b_i, c_i$ are integers.

For any $i, j$, $a_ix_j + b_iy_j \ne c_i$, meaning no point lies on the line.

For any $i \ne j$, $\left(\frac{a_i}{b_i}, \frac{c_i}{b_i}\right) \ne \left(\frac{a_j}{b_j}, \frac{c_j}{b_j}\right)$, meaning no two lines are identical.

The data is divided into 8 subtasks, each with fixed $n, m$ and an allowed cost limit. Each subtask may depend on others; you only receive points for a subtask if you pass all test cases for that subtask and its dependencies.

Subtask 5 satisfies special constraints: $-2^7 \le x_i < 2^7$, $-2^7 \le y_i < 2^7$, and for any $i \ne j$, $(x_i, y_i) \ne (x_j, y_j)$, meaning no two points coincide.

Subtask 6 satisfies special constraints: for $0 \le i < n, 0 \le j < m$, $x_i = 0$, $y_i = 2i$, $a_j = 0$, $|b_j| = 1$.