Problem Description

Given $n$ points $(x_i,y_i,c_i)$, $i=1,2,\dots,n$. There are $m$ query operations. In each query, $A,B,C$ are given. You need to find 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 line contains one integer, the answer to the corresponding query.

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

Idea: nzhtl1477, Solution: ccz181078, Code: ccz181078, Data: ccz181078.

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, for every $i$, $\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, and the subtasks are independent.

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 chosen uniformly at random 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 chosen independently at random, but the distribution of $c_i$ has no special restrictions.

Translated by ChatGPT 5