問題文
在二维平面上, (x_i,y_i) 到 r_i 的曼哈顿距离恰好为的点的集合组成的图形有 n 个。 无论哪 2 个图形,它们构成的点集合都没有公共部分。
此时,回答“从坐标 (x1,y1) 移动到坐标 (x2,y2) 时必须经过的最少点数”的查询 m 个,请依次回答。 由查询给出 2 个坐标保证不包含在任何图形的点集中。
移动时,可以移动相似的实数坐标。
入力
输入是按以下格式从标准输入给出的。
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
- 1 行表示图形数量的整数 n (1 ≦ n ≦ 10^5) 。
- 1 从行 n 行表示每个图形的信息 3 整数 x_i,y_i,r_i (-10^8 ≦ x_i,y_i ≦ 10^8, 1 ≦ r_i ≦ 10^8) 给出。任意两个图形所构成的点集没有交集。
- n+1 行表示查询的数量整数 m (1 ≦ m ≦ 10^5) 。
- n+2 从行 m 行表示每个查询的两个信息 4 整数 x1_i,y1_i,x2_i,y2_i (-10^8 ≦ x1_i,y1_i,x2_i,y2_i ≦ 10^8) 给出。这两个坐标保证不包含在任何图形的点集中。
出力
从第1行开始 m 按照给定顺序以换行符分隔输出各库里里的答案。最后一行也要换行。
入力例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
出力例1
4 2 0 5
表示输入输出示例1的图如下。
入力例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
出力例2
2 2 1 3
表示输入输出示例2的图如下。