题目描述

有一张 $n \times n$ 的矩形地图，地图上有 $m$ 颗地雷。第 $i$ 颗地雷的位置为 $(x_i, y_i)$，侦察半径为 $r_i$。在某个位置 $(x, y)$ 放置扫雷针，可以侦察到所有满足 $|x - x_i| + |y - y_i| \le r_i$ 的地雷（即曼哈顿距离不超过 $r_i$ 的地雷）。

现在有 $q$ 次询问，每次询问给出一个位置 $(x, y)$，请回答在该位置放置扫雷针可以侦察到多少颗地雷。

输入格式

第一行两个整数 $n, m$，分别表示地图大小和地雷数量。

接下来 $m$ 行，每行三个整数 $x_i, y_i, r_i$，表示一颗地雷的位置和侦察半径。

接下来一行一个整数 $q$，表示询问次数。

接下来 $q$ 行，每行两个整数 $x, y$，表示一次询问的位置。

输出格式

对于每次询问，输出一行一个整数，表示该位置能侦察到的地雷数量。

样例

3 2
3 3 2
2 2 1
3
1 1
2 2
3 3

0
2
1

5 3
1 1 2
3 3 2
5 5 2
4
1 1
3 3
5 5
3 1

1
1
1
2

样例解释

对于样例 1：地图 3×3，两颗地雷。

• 询问 (1,1)：雷 1 距离 $|3-1|+|3-1|=4 > 2$，雷 2 距离 $|2-1|+|2-1|=2 > 1$，均不可侦察，0。
• 询问 (2,2)：雷 1 距离 |3-2|+|3-2|=2 ≤ 2，雷 2 距离 |2-2|+|2-2|=0 ≤ 1，共 2 颗。
• 询问 (3,3)：雷 1 距离 0 ≤ 2 可侦察，雷 2 距离 |2-3|+|2-3|=2 > 1 不可侦察，共 1 颗。

对于样例 2：三颗地雷半径均为 2。

• (1,1)：雷 1 距 0 ≤ 2 可侦察，共 1 颗。
• (3,3)：雷 2 距 0 ≤ 2 可侦察，雷 1 距 4 > 2 不可，雷 3 距 4 > 2 不可，共 1 颗。
• (5,5)：雷 3 距 0 ≤ 2 可侦察，共 1 颗。
• (3,1)：雷 1 距 |3-1|+|1-1|=2 ≤ 2，雷 2 距 |3-3|+|1-3|=2 ≤ 2，共 2 颗。

数据范围与约定

提示：子任务 $3$ 输入量较大，请使用较快的输入输出方式。

下发样例

下发样例下载