Problem Description

Xiaoxue and Keke are trapped in an infinite-sized maze.

It is known that this maze has $N$ circular walls. If the entire maze is considered as a two-dimensional plane, then each wall is a circle on this plane. No two circles intersect, overlap, or are tangent, but they may contain each other. Xiaoxue and Keke are trapped at two different locations, and their positions are guaranteed not to coincide with any of these circles.

They can only pass through the walls by breaking them.

Xiaoxue wants to know the minimum number of walls they need to break in order to meet each other. They can meet at any location.

Input Format

The first line contains an integer $N$, indicating the number of walls.

The next $N$ lines each contain three integers $x, y, r$, indicating that there is a circular wall with center $(x, y)$ and radius $r$.

The next line contains an integer $Q$, indicating the number of queries.

The next $Q$ lines each contain four integers $a, b, c, d$, providing a query where Xiaoxue's position is $(a, b)$ and Keke's position is $(c, d)$.

Output Format

Output $Q$ lines, corresponding to the $Q$ queries. Each line should output an integer indicating the minimum number of walls that need to be broken for them to meet.

Sample Input and Output

Input Sample #1

3
0 0 1
3 0 1
2 0 4
1
0 0 3 0

Output Sample #1

2

Input Sample #2

3
0 0 1
0 0 2
4 0 1
2
0 0 4 0
0 0 0 4

Output Sample #2

3
2

Notes

For $20\%$ of the data, $0 \le N \le 200$.

For $40\%$ of the data, $0 \le N \le 1000$.

For $100\%$ of the data, $0 \le N, Q \le 8000, -10^8 \le x, y, r, a, b, c, d \le 10^8$.

Additionally, there are extra $20\%$ of the data satisfying $0 \le N \le 1000, 0 \le Q \le 1000$.

The time limit for large data points is $3$ seconds.

见题面 Input 部分

见题面 Output 部分