暂无测试数据。

rize 是一个可爱的女孩子。

一天，rize 进行了炮击的练习。炮击用的靶子为一个圆，其中有 $n-1$ 个与靶子同心的圆，将靶子划分成了 $n$ 个区域。这些区域里到外从 $1$ 到 $n$ 编号，第 $i$ 个区域的外径为 $R_i$ 。每个区域有一个分数，第 $i$ 个区域的分数为 $s_i$ 。rize 发射了 $m$ 枚炮弹。在靶平面上的以靶心为原点的直角坐标系下，第 $i$ 枚炮弹击中的区域为一个半径为 $r_i$ 的圆，其圆心的坐标为 $(x_i, y_i)$ 。若一枚炮弹击中的区域与靶子中的某个区域存在交集，则发射这枚炮弹会得到这个区域的分数。这里的区域不包含边界。

rize 想知道发射每一枚炮弹的得分。

输入格式

第一行两个数 $n, m$ ；

之后 $n$ 行，每行两个整数 $R_i, s_i$ ；

之后 $m$ 行，每行三个整数 $x_i, y_i, r_i$ 。

输出格式

$m$ 行，每行一个数表示答案。

数据范围

有 $30\%$ 的数据 $n, m \le 1000$ ；

另有 $20\%$ 的数据 $r_i = 1$ ；

另有 $20\%$ 的数据 $s_i = 1$ ；

对于 $100\%$ 的数据，$1 \le n, m \le 2 \times 10^5$，$1 \le s_i \le 10^4$，$-10^7 \le x_i, y_i \le 10^7$，$1 \le r_i \le 10^7$，$1 \le R_1 < R_2 < \cdots < R_n \le 10^7$。

3 3
1 2
2 2
3 1
3 -1 1
-2 -1 1
2 -4 2

1
3
1