← 返回题目列表

Codeforces · 1681/E

E. 迷宫冒险

中文机器翻译题面 查看原题

你发现了一张形状怪异的迷宫的地图。该地图是一个网格,由 $$$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

注意

这是第二个例子中的迷宫地图。门被标记为红色。