CF1681E.Labyrinth Adventures

You found a map of a weirdly shaped labyrinth. The map is a grid, consisting of $n$ rows and $n$ columns. The rows of the grid are numbered from $1$ to $n$ from bottom to top. The columns of the grid are numbered from $1$ to $n$ from left to right.

The labyrinth has $n$ layers. The first layer is the bottom left corner (cell $(1, 1)$). The second layer consists of all cells that are in the grid and adjacent to the first layer by a side or a corner. The third layer consists of all cells that are in the grid and adjacent to the second layer by a side or a corner. And so on.

The labyrinth with $5$ layers, for example, is shaped as follows:

The layers are separated from one another with walls. However, there are doors in these walls.

Each layer (except for layer $n$) has exactly two doors to the next layer. One door is placed on the top wall of the layer and another door is placed on the right wall of the layer. For each layer from $1$ to $n-1$ you are given positions of these two doors. The doors can be passed in both directions: either from layer $i$ to layer $i+1$ or from layer $i+1$ to layer $i$.

If you are standing in some cell, you can move to an adjacent by a side cell if a wall doesn't block your move (e.g. you can't move to a cell in another layer if there is no door between the cells).

Now you have $m$ queries of sort: what's the minimum number of moves one has to make to go from cell $(x_1, y_1)$ to cell $(x_2, y_2)$.

你发现了一张形状奇特的迷宫地图。该地图是一个 $n$ 行 $n$ 列的网格。网格的行从下到上编号为 $1$ 至 $n$，列从左到右编号为 $1$ 至 $n$。

该迷宫共有 $n$ 层。第 $1$ 层为左下角（即单元格 $(1, 1)$）。第 $2$ 层由所有在网格内、且与第 $1$ 层中任意单元格正交或对角相邻（即共享一条边或一个顶点）的单元格组成。第 $3$ 层由所有在网格内、且与第 $2$ 层中任意单元格正交或对角相邻的单元格组成。依此类推。

例如，一个具有 $5$ 层的迷宫形状如下所示：

各层之间由墙壁隔开，但这些墙壁上设有门。

除第 $n$ 层外，每一层均恰好有两扇通向下一层次的门：一扇位于该层的上侧墙上，另一扇位于该层的右侧墙上。对于从 $1$ 到 $n-1$ 的每一层，题目均给出这两扇门的位置。门是双向通行的：既可从第 $i$ 层经门进入第 $i+1$ 层，也可从第 $i+1$ 层经门返回第 $i$ 层。

若你位于某个单元格中，则仅当相邻（正交方向，即上下左右）单元格之间无墙壁阻挡时，方可移动至该相邻单元格（例如：若两个单元格分属不同层，且其间无门，则不可移动）。

现在你有 $m$ 个查询，每个查询形如：从单元格 $(x_1, y_1)$ 移动到单元格 $(x_2, y_2)$ 所需的最少步数是多少？

The first line contains a single integer $n$ ($2 \le n \le 10^5$) — the number of layers in the labyrinth.

The $i$-th of the next $n-1$ lines contains four integers $d_{1,x}, d_{1,y}, d_{2,x}$ and $d_{2,y}$ ($1 \le d_{1,x}, d_{1,y}, d_{2,x}, d_{2,y} \le n$) — the coordinates of the doors. Both cells are on the $i$-th layer. The first cell is adjacent to the top wall of the $i$-th layer by a side — that side is where the door is. The second cell is adjacent to the right wall of the $i$-th layer by a side — that side is where the door is.

The next line contains a single integer $m$ ($1 \le m \le 2 \cdot 10^5$) — the number of queries.

The $j$-th of the next $m$ lines contains four integers $x_1, y_1, x_2$ and $y_2$ ($1 \le x_1, y_1, x_2, y_2 \le n$) — the coordinates of the cells in the $j$-th query.

第一行包含一个整数 $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$ 层的上边界相邻（共享一条边）—— 该边即为第一扇门所在位置；第二个格子与第 $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$ 次查询中两个格子的坐标。

For each query, print a single integer — the minimum number of moves one has to make to go from cell $(x_1, y_1)$ to cell $(x_2, y_2)$.

对于每个查询，输出一个整数——从单元格 $(x_1, y_1)$ 移动到单元格 $(x_2, y_2)$ 所需的最少移动次数。

Here is the map of the labyrinth from the second example. The doors are marked red.

以下是第二个示例中迷宫的地图。门用红色标记。