Problem Description

Given $n$ points $(x_i, y_i, c_i)$, $i = 1, 2, \dots, n$. There are $m$ queries. Each query gives $A, B, C$, and asks for the number of ordered pairs $(i, j)$ such that $Ax_i + By_i + C < 0$, $Ax_j + By_j + C < 0$, and $c_i = c_j$.

Input Format

The first line contains two integers $n\ m$.

The next $n$ lines each contain three integers $x_i\ y_i\ c_i$, $i = 1, 2, \dots, n$.

The next $m$ lines each contain three integers $A\ B\ C$.

Output Format

Output $m$ lines, each containing one integer, representing the answer.

5 2
2 -1 1
0 -3 5
1 -3 2
1 3 5
3 2 2
1 2 4
1 -2 -9

2
9

Hint

Sample explanation:

The first query corresponds to $(2, 2)(3, 3)$.

The second query corresponds to $(1, 1)(2, 2)(2, 4)(3, 3)(3, 5)(4, 2)(4, 4)(5, 3)(5, 5)$.

Constraints:

For $5\%$ of the testdata, $n, m \le 10^3$.

For another $10\%$ of the testdata, $c_i \le 2$.

For another $15\%$ of the testdata, $c_i \le 100$.

For another $15\%$ of the testdata, $\max(|x_i|, |y_i|) = 10^6$.

For another $15\%$ of the testdata, $|A| = |B| = 1$.

For another $10\%$ of the testdata, $n \le 20000,\; m \le 200000$.

For the remaining testdata, there are no special constraints.

Each part of the testdata forms a subtask, with no dependencies.

All testdata satisfy:

$1 \le n \le 50000$.

$1 \le m \le 500000$.

$A^2 + B^2 > 0$.

$-10^9 \le x_i, y_i, A, B, C \le 10^9$.

$1 \le c_i \le n$.

All values are integers.

When $i \ne j$, $x_i \ne x_j$ or $y_i \ne y_j$.

For all testdata except Subtask 4, the $x, y$ coordinates of the $n$ points are independently and uniformly randomly chosen within some preset intervals, and it is guaranteed that there are no duplicate points. For the $i$-th point, $c_i$ and $x_i, y_i$ are independently randomly chosen, but the distribution of $c_i$ has no special restrictions.

Translated by ChatGPT 5