Given $n$ distinct points $(x_i, y_i)$, there are $m$ queries. Each query provides $A, B, C$, and asks for the number of pairs $(i, j)$ such that $x_i < x_j$, $y_i < y_j$, $Ax_i + By_i + C > 0$, and $Ax_j + By_j + C > 0$.

Input

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

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

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

Output

For each query, output a single line containing an integer representing the answer to the query.

Examples

Input 1

5 2
2003 -553
-141 1230
-6854 9658
9319 -1777
7773 3306
1113 -3086 -15864589
162 550 -21287

Output 1

0
1

Subtasks

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

For $100\%$ of the data, $A^2 + B^2 > 0$, $|A|, |B|, |C| \le 10^8$, $1 \le n, m \le 2 \times 10^5$, $|x_i|, |y_i| \le 10^4$. The points $(x_i, y_i)$ are chosen uniformly at random, but it is guaranteed that there are no duplicate points.

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

For another $25\%$ of the data, $A = 0$.

For another $25\%$ of the data, $C = 0$.

For the remaining $25\%$ of the data, there are no special restrictions.