Half-Plane Intersection Sum Query

You are given a custom data type Data which forms a commutative group \((D,+,-,e)\). That is, for any \(a,b,c \in D\) the following properties hold:

• \(a+b, a-b \in D\)
• Associativity: \((a+b)+c = a+(b+c)\)
• Commutativity: \(a+b = b+a\)

There exists an identity element \(e\) such that for every \(a\in D\):

• \(a+e = e+a = a\)
• \(a+(e-a) = (e-a)+a = e\)
• Also note that \(a-b = a+(e-b)\).

This problem provides you with a set of n points. The \(i\)th point has coordinates \((x_i, y_i)\) and an associated weight \(d_i\) of type Data (which you can think of as an integer for this problem). You are also given m half-planes, each described by three integers \((A, B, C)\). Finally, there are q queries. In the \(i\)th query, you are given two indices \(l_i\) and \(r_i\), and you must compute the sum of the weights of all points that lie in the intersection of the half-planes with indices from \(l_i\) to \(r_i\) (both inclusive).

Formally, for a query with parameters \(l\) and \(r\), define the set \[ S = \{ k \mid \forall j \; (l \le j \le r),\; A_j \times x_k + B_j \times y_k \ge C_j \}\]. The answer for this query is \[ \bigoplus_{k \in S} d_k, \] where \(\oplus\) denotes the group addition. In this problem, you can simply assume that the group operation is integer addition, the identity element is 0, and subtraction is the usual subtraction. (The provided Data class and its member functions add, sub, and clr correspond to these operations.)

Note for Local Testing: Your local testing must include #include <data.h>. However, when submitting your solution you should directly embed the following template in your code without including data.h:

class Data{
	friend int main();
  private:
	unsigned short x1,x2,x3,x4;
  public:
	void add(const Data &a,const Data &b);
	void sub(const Data &a,const Data &b);
	void clr();
};
void solve(
	int n,
	int xy[][2],
	Data d[],
	int m,
	int abc[][3],
	int q,
	int lr[][2],
	Data ans[]);

However, for the purpose of this problem, you can treat Data as an integer type and use normal arithmetic operations.

inputFormat

The input is given in the following format:

1. An integer n representing the number of points.
2. n lines follow, each containing three space-separated integers: xi, yi, and di (the weight of the point).
3. An integer m representing the number of half-planes.
4. m lines follow, each containing three space-separated integers: A, B, and C, describing a half-plane condition \(A\cdot x+B\cdot y \ge C\).
5. An integer q representing the number of queries.
6. q lines follow, each containing two space-separated integers l and r (1-indexed), representing the range of half-planes to consider.

It is guaranteed that the indices provided in queries are valid.

outputFormat

For each query, output a single integer on a new line — the sum of the weights of all points that satisfy all the half-plane conditions in the given range.

sample

3
0 0 1
1 1 2
2 0 3
2
1 0 0
0 1 0
2
1 1
1 2

6
6

</p>