Problem Description

In a two-dimensional plane, there are $n$ shapes consisting of sets of points where the Manhattan distance from $(x_i, y_i)$ is exactly $r_i$. For any two shapes, their point sets do not intersect.

You are given $m$ queries asking for the minimum number of points that must be traversed when moving from coordinate $(x1, y1)$ to coordinate $(x2, y2)$. The coordinates given in the queries are guaranteed not to be part of any shape's point set.

You can assume that you can move through any real coordinate during the movement.

Input Format

The input is given from the standard input in the following format:

$n$ $x_1$ $y_1$ $r_1$ $x_2$ $y_2$ $r_2$ : $x_n$ $y_n$ $r_n$ $m$ $x1_1$ $y1_1$ $x2_1$ $y2_1$ $x1_2$ $y1_2$ $x2_2$ $y2_2$ : $x1_m$ $y1_m$ $x2_m$ $y2_m$

• The first line contains an integer $n$ representing the number of shapes $(1 ≦ n ≦ 10^5)$.
• The next $n$ lines contain three integers each, $x_i, y_i, r_i$ $(-10^8 ≦ x_i, y_i ≦ 10^8, 1 ≦ r_i ≦ 10^8)$, representing the information of each shape. The point sets of any two shapes do not intersect.
• The $(n+1)$-th line contains an integer $m$ representing the number of queries $(1 ≦ m ≦ 10^5)$.
• The next $m$ lines contain four integers each, $x1_i, y1_i, x2_i, y2_i$ $(-10^8 ≦ x1_i, y1_i, x2_i, y2_i ≦ 10^8)$, representing the information of each query. These coordinates are guaranteed not to be part of any shape's point set.

Output Format

From the first line to the $m$-th line, output the answers to each query in the given order, separated by newlines. Ensure a newline at the end of the last line.

Sample Input and Output

Sample Input #1

5
0 0 1
0 0 5
0 0 9
0 0 13
20 20 1
4
0 0 13 13
0 0 0 7
0 2 0 3
0 0 20 20

Sample Output #1

4
2
0
5

Sample Input #2

6
0 0 10
0 5 4
5 0 4
0 -5 4
-5 0 4
8 8 2
4
0 5 0 -5
6 0 10 10
-5 0 0 0
5 0 8 8

Sample Output #2

2
2
1
3

Notes/Hints

Sample Explanation 1

The diagram representing Sample Input/Output #1 is as follows:

Sample Explanation 2

The diagram representing Sample Input/Output #2 is as follows:

见题面 Input 部分

见题面 Output 部分