AT_code_festival_final_i Shapes

在二维平面上有 $n$ 个图形，每个图形是由所有与某个点 $(x_i, y_i)$ 的曼哈顿距离正好为 $r_i$ 的点组成的。任意两个图形之间没有重叠区域。 接下来有 $m$ 个查询，要求计算从某个坐标点 $(x1, y1)$ 到另一个坐标点 $(x2, y2)$ 的最短路径上必须经过的点数。需要注意的是，查询中提供的坐标保证不在任何一个图形内。 移动过程中，可以经过任何实数坐标点。

输入通过标准输入提供，格式如下： > $ 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 $ - 第一行有一个整数 $n$，表示图形数量 $(1 \leq n \leq 10^5)$。 - 接下来的 $n$ 行中，每行有三个整数 $x_i, y_i, r_i$，描述每个图形的信息 $(-10^8 \leq x_i, y_i \leq 10^8, 1 \leq r_i \leq 10^8)$。这些图形之间没有重叠区域。 - 第 $n+1$ 行有一个整数 $m$，表示查询数目 $(1 \leq m \leq 10^5)$。 - 接下来的 $m$ 行中，每行有四个整数 $x1_i, y1_i, x2_i, y2_i$，描述每个查询的起点和终点。该坐标保证不在任何图形内 $(-10^8 \leq x1_i, y1_i, x2_i, y2_i \leq 10^8)$。

对于每个查询，按输入顺序输出结果，每个结果占一行。即使是最后一行也需要包含换行符。 **本翻译由 AI 自动生成**

### Sample Explanation 1 入出力例1を表した図は以下の通りです． !\[\](http://code-festival-2014-final.contest.atcoder.jp/img/other/code\_festival\_2014/I\_sample1.png) ### Sample Explanation 2 入出力例2を表した図は以下の通りです． !\[\](http://code-festival-2014-final.contest.atcoder.jp/img/other/code\_festival\_2014/I\_sample2.png)