Migrated from Lutece 3048 圆形抽象画

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

TAG：扫描线

为了追求独一的美，制作一个圆形抽象画是一个非常好的方法。

可以被视为二维笛卡尔坐标系的无限大的画布中，有 $n$ 个相离或内含的圆，第$i$个圆的圆心坐标为 $(x_i,y_i)$，其半径为 $r_i$ 。

制作一个圆形抽象画有两个步骤。第一步是在无限大的画布上切割下一个圆形画布，这个圆形画布的边界只会与画布上的圆相离或内含。此时，这个切下来的圆形画布以内部的圆为边界被分成了若干个区域。第二步是给这个圆形画布染色。初始时这个圆形画布上所有区域均为白色，尽可能多地选择一些区域染成绿色，同时需要保证任意两个绿色区域没有共用的边界（白色区域可以共用边界）。

现在给出了 q 个切割画布的方案，每个方案由切割的圆形圆心和半径组成，请给出每个方案需要染色成绿色的区域数量。

Input

第一行包括两个整数 $n,q$ ，$n$ 代表无限大画布上圆的数量，$q$ 代表给出的方案数。

接下来的 $n$ 行每行包含三个整数 $x_i,y_i,r_i$, 分别表示画布上圆的圆心坐标和半径

接下来的 $q$ 行每行包含三个整数 $x_i,y_i,r_i$, 分别表示切割画布的方案的圆的圆心坐标和半径

Output

输出一共 $q$ 行，每行包括一个整数 $ans_i$ ，表示第 $i$ 个方案需要染色成绿色的区域数量。

Samples

3 5
0 0 100
0 50 20
0 -50 20
0 0 80
0 0 2
500 0 2
0 50 25
0 0 150

2
1
1
1
3

Constraints

$1≤n,q≤10^5$

$-10^7≤x_i,y_i≤10^7$

$1≤r_i≤10^7$

Note

Resources

2023 UESTC ICPC Training for Geometry