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

Input

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

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

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

Output

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

Examples

Input 1

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

Output 1

2
9

Note 1

The first query corresponds to $(2, 2)$ and $(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)$.

Subtasks

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

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

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

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

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

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

For the remaining data, there are no special constraints.

Each part of the data constitutes a subtask, and there are no dependencies between them.

All data 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 \neq j$, $x_i \neq x_j$ or $y_i \neq y_j$.

For all data except for subtask 4, the $x$ and $y$ coordinates of the $n$ points are chosen uniformly at random within certain preset intervals, ensuring no duplicate points. For the $i$-th point, $c_i$ and $(x_i, y_i)$ are chosen independently at random, but there are no special restrictions on the distribution of $c_i$.