This is an interactive problem. You need to implement the solve() function using the Data class. You may use the member functions add(), sub(), and clr() of the Data class, as well as functions automatically synthesized by the C++ compiler (including constructors and assignment operators).

Let $D$ be the set of all elements of type Data.

For any $a, b, c \in D$, the following properties hold:

• $a+b, a-b \in D$
• $(a+b)+c=a+(b+c)$
• $a+b=b+a$

There exists an identity element $e \in D$ such that for any $a, b \in D$, the following properties hold:

• $a+e=e+a=a$
• $a+(e-a)=(e-a)+a=e$
• $a-b=a+(e-b)$

The above properties can also be stated as: $(D, +, -, e)$ forms an abelian group.

You are given $n$ points, where the $i$-th point has coordinates $(x_i, y_i)$ and a weight $d_i$ of type Data, for $i=1, 2, \dots, n$.

You are given $m$ half-planes $(A_i, B_i, C_i)$, for $i=1, 2, \dots, m$.

There are $q$ queries $(l_i, r_i)$, for $i=1, 2, \dots, q$.

For each query $i$, you need to calculate the sum of weights of the points contained in the intersection of the given range of half-planes. Specifically:

Let $S_i = \{ k \mid \forall l_i \le j \le r_i, A_jx_k + B_jy_k \ge C_j \}$. Calculate $\sum\limits_{k \in S_i} d_k$.

Interaction

Use the a.clr() function to set $a$ to the identity element $e$.

Use the a.add(b, c) function to set $a$ to $b+c$.

Use the a.sub(b, c) function to set $a$ to $b-c$.

Use a=b to set $a$ to $b$.

Implementation Details

The interface for the solve function you need to implement is as follows:

void solve(
    int n,
    int xy[][2],
    Data d[],
    int m,
    int abc[][3],
    int q,
    int lr[][2],
    Data ans[]);

During evaluation, the interactor will call solve exactly once.

In the parameters of the solve function, $x_i$ corresponds to xy[i][0], $y_i$ corresponds to xy[i][1], and $d_i$ corresponds to d[i].

$A_i, B_i, C_i$ correspond to abc[i][0], abc[i][1], abc[i][2].

$l_i, r_i$ correspond to lr[i][0], lr[i][1], and the answer to the $i$-th query must be stored in ans[i].

$n, m, q$ correspond to n, m, q.

You may perform any number of assignments, copies, or calls to the clr() function, but the total number of calls to add() and sub() must not exceed $4\times 10^7$.

For C++ users, please ensure your program starts with:

#include "data.h"

The grader.cpp provided in the problem directory is a reference implementation of the interactor. The interactor used for final testing will differ from this reference implementation, so your solution should not rely on the specific implementation of the interactor.

For C++ users:

You must name your submission file chesed.cpp and compile it in the problem directory using the following command:

g++ grader.cpp chesed.cpp -o chesed -O2 -lm

For the resulting executable:

It will first read the data from the input file of the test case.

After reading is complete, the interactor will call the solve function exactly once to test your function with the input data.

After your function returns correctly, the interactor will output the answers for each query to the output file based on your results. If your output matches the output file of the test case exactly (ignoring trailing spaces), you pass the test case.

Constraints

For $25\%$ of the data, $n, m, q \le 100$.

For another $25\%$ of the data, $q \le 100$.

For another $25\%$ of the data, $l_i=r_i$, and $x_i, y_i$ are chosen independently and uniformly at random within the given range.

For $100\%$ of the data, $1 \le n \le 2\times 10^5$, $1 \le m \le 10^4$, $1 \le q \le 10^5$, $|A_j|, |B_j| \le 10^4$, $|x_i|, |y_i|, |C_j| \le 10^5$, $B_j > 0$, $-10^6 \le C_j < 0$, $1 \le l_i \le r_i \le m$.