Description

Inspired by the great painter Picasso, Vera decided to create her masterpiece. She has a canvas that can be simplified as an infinitely large 2D plane. Vera likes integer powers of $2$ $(1,2,4,8,16,\ldots)$, and she will color some points using step sizes that are powers of $2$.

Vera will color $n$ times. The $i$-th coloring operation is described by three integers $x_i, y_i, v_i$. Let $a_i$ be the largest power of $2$ that is not greater than $x_i$, and let $b_i$ be the largest power of $2$ that is not greater than $y_i$. Vera will use color $v_i$ to color all points with coordinates $(x_i + a_i p, y_i + b_i q)$, where $p, q$ are non-negative integers. A point may be colored multiple times with different colors, and it may also be colored multiple times with the same color. The color value of a point is the sum of all colors that have been applied to that point.

Then Vera will ask $Q$ questions. For the $j$-th question, she wants to know the color value of the point at coordinates $(r_j, c_j)$. If a point has never been colored, then its color value is $0$.

Because you are forced to be Vera's assistant, you have to answer Vera's questions.

Input Format

The first line contains two integers $n, Q$, separated by a space.

The next $n$ lines each contain three integers $x_i, y_i, v_i$ separated by spaces, meaning that the coloring operation described in the statement is performed using color $v_i$, with parameters $x_i$ and $y_i$.

The next $Q$ lines each contain two integers $r_j, c_j$ separated by spaces, asking for the color value of the point $(r_j, c_j)$.

Output Format

Output $Q$ lines. Each line contains one integer. The integer on the $j$-th line is the color value of the point $(r_j, c_j)$.

5 6
1 2 1
3 4 2
4 5 3
6 3 4
7 1 5
2 6
7 8
5 9
11 2
10 7
4 5

1
8
0
6
4
3

Hint

Sample Explanation

Let colors $1,2,3,4,5$ be red, blue, green, orange, and purple, respectively.

Let $p, q$ be non-negative integers. Then:

• Points with coordinates $(1 + p, 2 + 2q)$ are colored red.
• Points with coordinates $(3 + 2p, 4 + 4q)$ are colored blue.
• Points with coordinates $(4 + 4p, 5 + 4q)$ are colored green.
• Points with coordinates $(6 + 4p, 3 + 2q)$ are colored orange.
• Points with coordinates $(7 + 4p, 1 + q)$ are colored purple.

The coordinate grid from $(0,0)$ to $(11,11)$ is shown in the figure:

We can observe that:

• $(2,6)$ is colored red, so its color value is $1$.
• $(7,8)$ is colored red, blue, and purple, so its color value is $1+2+5=8$.
• $(5,9)$ is not colored, so its color value is $0$.
• $(11,2)$ is colored red and purple, so its color value is $1+5=6$.
• $(10,7)$ is colored orange, so its color value is $4$.
• $(4,5)$ is colored green, so its color value is $3$.

Constraints and Notes

• For $20\%$ of the testdata, $1 \le n, Q \le 2 \times 10^3$.
• For another $20\%$ of the testdata, $y_i = 1 \ (1 \le i \le n)$.
• For another $20\%$ of the testdata, $1 \le n, Q \le 10^5$ and $1 \le r_j, c_j \le 10^9 \ (1 \le j \le Q)$.
• For $100\%$ of the testdata, $1 \le n, Q \le 2 \times 10^5$, $1 \le i \le n$, $1 \le v_i \le 10^4$, $1 \le x_i, y_i, r_j, c_j \le 10^{18}$, and $1 \le j \le Q$.

Due to issues with the judging machine, only the last $10$ test cases are kept.

Source: CCO 2017 Day 1 “ Vera and Modern Art ”.

Note: This translation is from LOJ.

Translated by ChatGPT 5