拜托尼亚（Bajtocja）已实现移动通信覆盖。电信中继站被放置在全国各地的不同点。第 $i$ 个中继站位于坐标 $(x_i, y_i)$ 处，其信号强度为 $s_i$。在其他点，信号强度随距离中继站的距离线性衰减，其中距离采用切比雪夫距离（maximum metric）度量。这意味着在点 $(x + d_x, y + d_y)$ 处，来自第 $i$ 个中继站的信号强度为 $\max(0, s_i - \max(|d_x|, |d_y|))$。

我们假设某一点的覆盖强度等于所有放置在拜托尼亚的中继站信号强度的最大值。

请编写一个程序，计算给定点处的覆盖强度。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 300\,000$)，分别表示中继站的数量和需要处理的查询数量。

接下来的 $n$ 行描述中继站：第 $i$ 行包含三个整数 $x_i, y_i$ 和 $s_i$ ($-10^{18} \le x_i, y_i \le 10^{18}, 1 \le s_i \le 10^{18}$)，表示第 $i$ 个中继站位于坐标 $(x_i, y_i)$，其信号强度参数为 $s_i$。

接下来的 $m$ 行描述查询：第 $i$ 行包含两个整数 $x'_i$ 和 $y'_i$ ($-10^{18} \le x'_i, y'_i \le 10^{18}$)，表示我们对坐标为 $(x'_i, y'_i)$ 的点的覆盖强度感兴趣。

每个点最多放置一个中继站。此外，每个点最多对应一个查询。

输出格式

输出 $m$ 行：第 $i$ 行应包含一个整数，表示坐标为 $(x'_i, y'_i)$ 的点的覆盖强度。

样例

输入 1

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

输出 1

2
1
0

说明 1

在坐标 $(6, 3)$ 处，第一个中继站的信号强度为 $2$，第二个为 $1$，因此覆盖强度为 $2$。在坐标 $(7, 1)$ 处，两个中继站的信号强度均为 $1$，因此覆盖强度为 $1$。坐标 $(12, 5)$ 距离中继站足够远，覆盖强度为 $0$。

评测测试

以下是用于评测的测试用例描述：

1. $n = 3, m = 6$。中继站位于坐标 $(-1, -1), (0, 0)$ 以及 $(1, 1)$，每个中继站的信号强度参数均为 $3$。查询点位于连接 $(-2, -3)$ 和 $(3, 2)$ 的线段上。

2. $n = 33, m = 100$。所有查询和中继站均包含在对角顶点为 $(1, 1)$ 和 $(10, 10)$ 的正方形内。中继站位于坐标和能被 $3$ 整除的点上。第 $i$ 个中继站的信号强度等于 $x_i + y_i$ 的约数之和。

3. $n = 300\,000, m = 300\,000$。第 $i$ 个中继站位于坐标 $(-10^{18} + (2i-2) \cdot 10^9, 0)$，第 $i$ 个查询点位于坐标 $(-10^{18} + (2i-1) \cdot 10^9, 0)$。每个中继站的信号强度参数均为 $10^{18}$。

评分标准

测试集分为以下子任务。每个子任务的测试由一组或多组独立的测试用例组成。