一个位于北极深处冰封湖面上的渔村正受到全球变暖的威胁——湖面上开始出现裂缝。该村庄由 $n$ 个球形的冰屋组成，每个冰屋占据湖面上的一个圆形区域。

一个冰屋可以在坐标平面上表示为一个圆：圆心为坐标为整数的点，半径为小于 1 且恰好有一位小数的正浮点数。

给定可能出现的冰裂缝位置，村民们想知道每个裂缝会影响多少个冰屋。形式化地说，给定 $q$ 次查询，每次查询为一个由两个端点定义的直线段，求每个线段与多少个冰屋相交。如果线段与圆的内部至少有一个公共点，则称该线段与冰屋相交。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 100\,000$)，表示冰屋的数量。接下来的 $n$ 行，每行包含三个数 $x, y$ 和 $r$，分别表示一个冰屋的圆心坐标和半径。坐标 $x$ 和 $y$ 为整数，满足 $1 \le x, y \le 500$，$r$ 为恰好有一位小数的浮点数，满足 $0 < r < 1$。任意两个冰屋不会相交或相切。

接下来的一行包含一个整数 $q$ ($1 \le q \le 100\,000$)，表示查询的数量。接下来的 $q$ 行，每行包含四个整数 $x_1, y_1, x_2, y_2$ ($1 \le x_1, y_1, x_2, y_2 \le 500$)，表示线段的两个端点坐标。两个端点互不相同。端点可能位于冰屋内部。

你可以假设，对于每个冰屋 $i$ 和线段 $s$，线段 $s$ 到圆心 $i$ 的距离的平方要么小于 $r^2 - 10^{-5}$，要么大于 $r^2 + 10^{-5}$，其中 $r$ 是冰屋 $i$ 的半径。

输出格式

输出应包含 $q$ 行。第 $k$ 行应包含一个整数，表示与第 $k$ 个线段相交的冰屋数量。

样例

输入格式 1

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

输出格式 1

2
1