Vera and Modern Art

Inspired by the great painter Picowso, Vera decided to make her own masterpiece. Her canvas is an infinite two-dimensional coordinate plane. Vera likes powers of two (1, 2, 4, 8, 16, ...), so she paints points repeatedly with step sizes that are powers of two.

Vera paints $N$ times. The $i$-th time is described by three integers $x_i$, $y_i$, $v_i$. Let $a_i$ be the largest power of two not greater than $x_i$, and let $b_i$ be the largest power of two not greater than $y_i$. Vera adds one paint drop of colour $v_i$ to every point of the form $(x_i + a_i p,\ y_i + b_i q)$, where $p$ and $q$ are non-negative integers. A point may hold several paint drops, and several drops of the same colour.

Vera then asks $Q$ questions. The $j$-th question asks for the colour at the point $(r_j, c_j)$. The colour at a point is the sum of the colours of all paint drops on it. A point with no paint drop has colour 0.

You are her art assistant, so you have to answer the questions.

The first line contains two integers $N$ and $Q$, separated by one space ($1 \le N, Q \le 2 \cdot 10^5$).

Each of the next $N$ lines contains three space-separated integers $x_i$, $y_i$, $v_i$, describing the paint drops of colour $v_i$ ($1 \le i \le N$; $1 \le v_i \le 10000$; $1 \le x_i, y_i \le 10^{18}$).

Each of the next $Q$ lines contains two space-separated integers $r_j$ and $c_j$, describing a question about the point $(r_j, c_j)$ ($1 \le j \le Q$; $1 \le r_j, c_j \le 10^{18}$).

Print $Q$ lines. Line $j$ contains one integer, the colour of the point $(r_j, c_j)$.

In the first example, let colours 1, 2, 3, 4, 5 be red, blue, green, orange, purple. With $p$ and $q$ non-negative integers, the drops land as follows.

• A red drop on every point $(1 + p,\ 2 + 2q)$.
• A blue drop on every point $(3 + 2p,\ 4 + 4q)$.
• A green drop on every point $(4 + 4p,\ 5 + 4q)$.
• An orange drop on every point $(6 + 4p,\ 3 + 2q)$.
• A purple drop on every point $(7 + 4p,\ 1 + q)$.

The painting from $(0, 0)$ to $(11, 11)$ looks like this.

The point $(7, 8)$ has a red, a blue and a purple drop, so its colour is $1 + 2 + 5 = 8$. The point $(5, 9)$ has no drop, so its colour is 0.