题目描述

题目译自 XXVII Olimpiada Informatyczna – Eliminacje do IOI Przekaźniki telekomunikacyjne

拜托西亚全国已覆盖移动电话信号。电信中继器被安置在国内不同地点。第 $i$ 个中继器位于点 $(x_{i}, y_{i})$，其信号强度为 $s_{i}$。在其他地点，信号强度随距离线性下降，距离采用所谓的最大值度量方式计算。这意味着，在点 $(x + d_{x}, y + d_{y})$，来自第 $i$ 个中继器的信号强度为 $\max\left(0, s_{i} - \max\left(|d_{x}|, |d_{y}|\right)\right)$。

我们假设某点的信号覆盖强度等于来自拜托西亚所有中继器的信号强度的最大值。

请编写一个程序，计算国内指定点的信号覆盖强度。

输入格式

输入数据的第一行包含两个整数 $n$ 和 $m$ $(1 \leq n, m \leq 300000)$，分别表示中继器数量和查询数量。

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

接下来的 $m$ 行描述查询：第 $i$ 行包含两个整数 $x_{i}^{\prime}$ 和 $y_{i}^{\prime}$（$-10^{18} \leq x_{i}^{\prime}, y_{i}^{\prime} \leq 10^{18}$），表示需要查询坐标 $(x_{i}^{\prime}, y_{i}^{\prime})$ 处的信号覆盖强度。

每个点最多只有一个中继器。此外，每个点最多被查询一次。

输出格式

输出应包含 $m$ 行：第 $i$ 行应为一个整数，表示坐标 $(x_{i}^{\prime}, y_{i}^{\prime})$ 处的信号覆盖强度。

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

2
1
0

在点 $(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=300000$，$m=300000$。第 $i$ 个中继器位于坐标 $(-10^{18} + (2i-2) \cdot 10^{9}, 0)$，第 $i$ 个查询点位于坐标 $(-10^{18} + (2i-1) \cdot 10^{9}, 0)$。每个中继器的信号强度参数为 $10^{18}$。

数据范围与提示

详细子任务附加限制及分值如下表所示。