Ice Igloos

A fishing village built on the surface of a frozen lake in the far north is in danger from global warming: cracks are starting to form on the lake surface. The village consists of $n$ igloos of spherical shape, and each igloo covers a circular area of the surface.

An igloo can be represented as a circle in the coordinate plane. The centre of the circle is a point with integer coordinates, and the radius is a positive real number smaller than $1$ with exactly one digit after the decimal point.

Given the locations of possible cracks, the villagers want to know how many igloos each crack affects. Formally, you are given $q$ queries, and each query is a line segment defined by its two endpoints. For each segment, find the number of igloos it intersects. A segment intersects an igloo if the segment and the interior of the circle share at least one point.

The first line contains an integer $n$ ($1 \le n \le 100\,000$), the number of igloos. Each of the next $n$ lines contains three numbers $x$, $y$ and $r$, the coordinates of the centre and the radius of one igloo. The coordinates $x$ and $y$ are integers with $1 \le x, y \le 500$, and $r$ is a real number with exactly one digit after the decimal point such that $0 < r < 1$. No two igloos overlap or touch.

The next line contains an integer $q$ ($1 \le q \le 100\,000$), the number of queries. Each of the next $q$ lines contains four integers $x_1$, $y_1$, $x_2$, $y_2$ ($1 \le x_1, y_1, x_2, y_2 \le 500$), the coordinates of the two endpoints of one segment. The two endpoints are different. An endpoint may lie inside an igloo.

For every igloo $i$ and every segment $s$, the square of the distance between $s$ and the centre of $i$ is either smaller than $r^2 - 10^{-5}$ or greater than $r^2 + 10^{-5}$, where $r$ is the radius of igloo $i$.

Print $q$ lines. The $k$-th line contains the number of igloos that the $k$-th segment intersects.