题目描述

一个坐落在北极冰冻湖面上的渔村因全球变暖而面临危险——湖面开始破碎。村庄内有 $n$ 座球形冰屋，每座冰屋在湖面上占据了一块圆形区域。

一座冰屋可以视为平面座标系中的一个圆：其圆心座标为整数，其半径为小于 $1$ 的一位浮点数。给出冰面断裂的座标，这些村民希望知道每次断裂会有多少个冰屋受到影响。

形式上，给出 $q$ 个询问，每个询问包括一条由两个端点确定的线段，查询每条线段贯穿的冰屋数。如果线段与圆的内部有至少一个交点，则线段贯穿了这座冰屋。

输入格式

第一行包括一个整数 $n$——冰屋数。

接下来的 $n$ 行每行包括三个数 $x$，$y$ 和 $r$——冰屋的座标和半径。$x$ 和 $y$ 为整数且。$r$ 是一位浮点数。冰屋之间不存在重叠或接触。

你可以认为，对于任一冰屋 $i$ 和线段 $s$ 的距离的平方小于 $r_2 - 10^{-5}$ 或大于 $r_2 + 10^{-5}$。

输出格式

输出包括 $q$ 行。第 $k$ 行包括一个整数——被第 $k$ 条线段穿过的冰屋数。

5
4 2 0.6
7 3 0.7
8 5 0.8
1 3 0.7
3 4 0.4
2
3 1 9 6
3 4 7 2

2
1

数据范围与约定

对于 $100 \%$ 的数据， $1 \le n \le 10^5$，$1 \le x, y \le 500$，$0 \lt r \lt 1$。