宝可梦水族馆终于要重新装修了！为了纪念成立 5 周年，水族馆建造了一个大型的水景装饰！

这个装饰的设计非常有趣，可以建模为正方形区域 $(0, 0)$ 到 $(10^6, 10^6)$ 内的一系列互不重叠的圆。对于所有整数 $0 \le x_i \le 10^6$，在 $(x_i, \infty)$ 处都有一个直接向下洒水的洒水器。

水总是直接向下流动。如果它碰到了一个圆，它会根据碰到圆的位置而以不同的方式流动：

1. 如果它碰到圆的左半部分，它将沿着左侧流动，并从左半部分继续向下流动。
2. 如果它碰到圆的右半部分，它将沿着右侧流动，并从右半部分继续向下流动。
3. 如果它碰到圆的正上方，它将同时沿着圆的左侧和右侧流动，并从两边继续向下流动。

杰尼龟喜欢观察装饰中的水流。它想知道，如果激活 $x = L$ 到 $x = R$ 之间的所有洒水器，水在 $y = 0$ 处能到达多少个不同的 $x$ 坐标？给定 $Q$ 个查询，请帮助杰尼龟回答这个令人困惑的问题！

输入格式

输入的第一行包含两个整数 $N$ 和 $Q$。

接下来的 $N$ 行，每行包含三个整数 $x_i, y_i, r_i$，表示一个圆心在 $(x_i, y_i)$、半径为 $r_i$ 的圆。

接下来的 $Q$ 行，每行包含两个整数 $L_j, R_j$，表示第 $j$ 次查询，查询激活 $x = L_j$ 到 $x = R_j$ 之间的洒水器。

数据范围

• $1 \le N \le 10^5$
• $1 \le Q \le 2 \cdot 10^5$
• $1 < x_i, y_i < 10^6$
• $1 \le r_i \le 5 \cdot 10^5$
• $0 \le L_j, R_j \le 10^6$

保证所有圆都完全包含在左下角为 $(0, 0)$、右上角为 $(10^6, 10^6)$ 的正方形内，且所有圆互不相交。

输出格式

输出 $Q$ 个整数，其中第 $j$ 个整数表示如果激活 $x = L_j$ 到 $x = R_j$ 的洒水器，水流可以到达的不同的 $x$ 坐标的数量。

样例

输入样例 1

1 3
1 1 1
0 0
0 1
1 1

输出样例 1

1
2
2

输入样例 2

2 4
1 1 1
4 5 3
0 0
0 1
1 1
5 6

输出样例 2

1
2
2
1