Vera's Masterpiece

Inspired by Picasso, Vera decides to create her masterpiece on an infinite 2D canvas. Vera loves integer powers of 2 (i.e., $1,2,4,8,16,\dots$) and will perform $n$ coloring operations.

In the $i$-th coloring operation, three integers $x_i$, $y_i$, and $v_i$ are given. Define $$a_i=\max\{2^k\mid 2^k\le x_i\}, \quad b_i=\max\{2^k\mid 2^k\le y_i\}.$$ Then, Vera colors all points at coordinates $$ (x_i+a_i\cdot p,\;y_i+b_i\cdot q) $$ for all nonnegative integers $p$ and $q$, using the color value $v_i$. A point may be colored multiple times (even by the same color), and its final color is the sum of all applied color values.

After performing all coloring operations, Vera asks $Q$ queries. For the $j$-th query, you need to determine the color of the point at $(r_j,c_j)$. If a point is never colored, its color is $0$.

inputFormat

The first line contains two integers $n$ and $Q$. Each of the next $n$ lines contains three integers $x_i$, $y_i$, and $v_i$, describing a coloring operation. Each of the following $Q$ lines contains two integers $r_j$ and $c_j$, representing a query.

outputFormat

For each query, output a single integer — the color of the specified point.

sample

2 3
3 5 10
1 1 5
3 5
3 9
4 6

15
15
5