Byteotia has been covered by mobile phone coverage. Telecommunication transmitters have been placed at various points in the country. The signal strength at the point $(x_i, y_i)$, where the $i$-th transmitter is located, is $s_i$. At other points, the signal strength decreases linearly with the distance from the transmitter, where the distance is measured in the so-called maximum metric. This means that at the point $(x + d_x, y + d_y)$, the signal strength coming from the $i$-th transmitter is $\max(0, s_i - \max(|d_x|, |d_y|))$.

We assume that the coverage strength at a given point is equal to the maximum of the signal strengths from all transmitters placed in Byteotia.

Write a program that determines the coverage strength at given points in the country.

Input

The first line of the input contains two integers $n$ and $m$ ($1 \le n, m \le 300\,000$) denoting the number of transmitters and the number of queries to process, respectively.

The next $n$ lines contain descriptions of the transmitters: the $i$-th of them contains three integers $x_i, y_i$ and $s_i$ ($-10^{18} \le x_i, y_i \le 10^{18}$, $1 \le s_i \le 10^{18}$) meaning that the $i$-th transmitter is located at the point with coordinates $(x_i, y_i)$, and its signal strength parameter is $s_i$.

The next $m$ lines contain descriptions of the queries: the $i$-th of them contains two integers $x'_i$ and $y'_i$ ($-10^{18} \le x'_i, y'_i \le 10^{18}$) meaning that we are interested in the coverage strength at the point with coordinates $(x'_i, y'_i)$.

There is at most one transmitter at any single point. Furthermore, there is at most one query for any single point.

Output

Output $m$ lines: the $i$-th line should contain a single integer, which is the coverage strength at the point with coordinates $(x'_i, y'_i)$.

Examples

Input 1

2 3
3 2 5
8 3 3
6 3
7 1
12 5

Output 1

2
1
0

Note

At the point with coordinates $(6, 3)$, the signal strength of the first transmitter is $2$, and the second is $1$, which gives a coverage strength equal to $2$. At the point with coordinates $(7, 1)$, the signal strength of both transmitters, and thus the coverage strength, is $1$. The point with coordinates $(12, 5)$ is far enough from the transmitters that the coverage strength there is $0$.

Evaluation tests

1. $n = 3, m = 6$. Transmitters are located at $(-1, -1), (0, 0)$ and $(1, 1)$, and the signal strength parameter of each is $3$. Query points lie on the segment connecting $(-2, -3)$ and $(3, 2)$.
2. $n = 33, m = 100$. All queries and transmitters are contained within a square with opposite vertices at $(1, 1)$ and $(10, 10)$. Transmitters are located at points where the sum of coordinates is divisible by $3$. The strength of the $i$-th transmitter is equal to the sum of divisors of $x_i + y_i$.
3. $n = 300\,000, m = 300\,000$. The $i$-th transmitter is at $(-10^{18} + (2i-2) \cdot 10^9, 0)$, and the $i$-th query concerns the point $(-10^{18} + (2i-1) \cdot 10^9, 0)$. The signal strength parameter of each transmitter is $10^{18}$.

Subtasks