Description

In the Chocolate Kingdom, chocolates are made from milk and cocoa. However, not every piece of chocolate is favored by the people, because no one likes overly sweet chocolate.

For each piece of chocolate, let $x$ and $y$ be its milk and cocoa content. Since everyone has their own standard for sweetness, each person has two parameters $a$ and $b$, which are their weights for milk and cocoa, respectively. Therefore, for a chocolate with milk and cocoa content $x$ and $y$, its sweetness for that person is $ax+by$. Each person also has a sweetness threshold $c$: all chocolates with sweetness greater than or equal to $c$ are unacceptable to them. Each piece of chocolate has a deliciousness value $h$.

Now we want to know, for each person, the sum of the deliciousness values of the chocolates they can accept.

Input Format

The first line contains two positive integers $n$ and $m$, denoting the number of chocolates and the number of queries.
The next $n$ lines each contain three integers $x , y , h$, as described above.
Then the next $m$ lines each contain three integers $a , b , c$, as described above.

Output Format

Output $m$ lines, where the $i$-th line is the sum of the deliciousness values of the chocolates acceptable to the $i$-th person.

3 3
1 2 5
3 1 4
2 2 1
2 1 6
1 3 5
1 3 7

5
0
4

Hint

Constraints: For 100% of the testdata, $1<=n,m<=50000$,$-10^9<=a_i,b_i,x_i,y_i<=10^9$.

The testdata is guaranteed to be randomly generated in some manner.

Translated by ChatGPT 5