你发现了一张形状怪异的迷宫的地图。该地图是一个网格,由 $$$n$$$ 行和 $$$n$$$ 列组成。网格的行从下到上编号为 $$$1$$$ 到 $$$n$$$。网格的列从左到右编号为 $$$1$$$ 到 $$$n$$$。
迷宫有 $$$n$$$ 层。第一层位于左下角(单元格 $$$(1, 1)$$$)。第二层由网格中并通过边或角与第一层相邻的所有单元组成。第三层由网格中并通过边或角与第二层相邻的所有单元组成。等等。
以 $$$5$$$ 层的迷宫为例,其形状如下:
各层之间用墙壁隔开。然而,这些墙上有门。
每一层($$$n$$$ 层除外)都有两扇通往下一层的门。一扇门放置在该层的顶墙上,另一扇门放置在该层的右墙上。对于从 $$$1$$$ 到 $$$n-1$$$ 的每一层,您都会获得这两扇门的位置。门可以双向通过:从层 $$$i$$$ 到层 $$$i+1$$$ 或从层 $$$i+1$$$ 到层 $$$i$$$。
如果你站在某个牢房中,如果墙壁没有阻挡你的移动,你可以移动到旁边的相邻牢房(例如,如果牢房之间没有门,你就无法移动到另一层的牢房)。
现在您有 $$$m$$$ 类查询:从单元格 $$$(x_1, y_1)$$$ 到单元格 $$$(x_2, y_2)$$$ 需要移动的最少次数是多少。
输入
第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^5$$$) — 迷宫的层数。
接下来的 $$$n-1$$$ 行中的第 $$$i$$$ 包含四个整数 $$$d_{1,x}、d_{1,y}、d_{2,x}$$$ 和 $$$d_{2,y}$$$ ($$$1 \le d_{1,x}、d_{1,y}、d_{2,x}, d_{2,y} \le n$$$) — 门的坐标。两个单元都位于第 $$$i$$$ 层。第一个牢房与第 $$$i$$$ 层的顶墙有一侧相邻——那一侧就是门所在的位置。第二个牢房与第 $$$i$$$ 层的右墙相邻,一侧是门所在的位置。
下一行包含一个整数 $$$m$$$ ($$$1 \le m \le 2 \cdot 10^5$$$) — 查询数。
接下来的 $$$m$$$ 行的第 $$$j$$$ 包含四个整数 $$$x_1、y_1、x_2$$$ 和 $$$y_2$$$ ($$$1 \le x_1, y_1, x_2, y_2 \le n$$$) — 第 $$$j$$$ 查询中单元格的坐标。
输出
对于每个查询,打印一个整数 - 从单元格 $$$(x_1, y_1)$$$ 到单元格 $$$(x_2, y_2)$$$ 必须进行的最小移动次数。
示例
输入 #1
2 1 1 1 1 10 1 1 1 1 1 1 1 2 1 1 2 1 1 1 2 2 1 2 1 2 1 2 2 1 1 2 2 2 2 1 2 1 2 1 2 2 2 2 2 2
输出 #1
0 1 1 2 0 2 1 0 1 0
输入 #2
4 1 1 1 1 2 1 2 2 3 2 1 3 5 2 4 4 3 4 4 3 3 1 2 3 3 2 2 4 4 1 4 2 3
输出 #2
3 4 3 6 2
注意
这是第二个例子中的迷宫地图。门被标记为红色。