迷宫冒险

• 时间限制：5 秒
• 内存限制：512 MiB

题目描述

有一个 $n\times n$ 的方格迷宫，行从下到上、列从左到右编号。单元格 $(x,y)$ 属于第 $\max(x,y)$ 层。

相邻层之间有墙。第 $i$ 层与第 $i+1$ 层之间恰有两扇双向门：一扇位于第 $i$ 层顶部，另一扇位于第 $i$ 层右侧。给出所有门的位置后，需要回答若干两点间最短路询问。每次可以移动到共享一条边的相邻单元格；跨层时必须经过门。

输入格式

第一行包含整数 $n$。

接下来 $n-1$ 行，第 $i$ 行包含 $d_{1,x},d_{1,y},d_{2,x},d_{2,y}$。前两个坐标表示第 $i$ 层顶部门的内侧单元格，后两个坐标表示右侧门的内侧单元格。

下一行包含询问数 $m$。

接下来 $m$ 行，每行包含 $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\le n\le10^5$，$2\le m\le2\times10^5$。顶部门满足 $d_{1,x}=i,1\le d_{1,y}\le i$，右侧门满足 $d_{2,y}=i,1\le d_{2,x}\le i$；询问坐标均在 $[1,n]$ 内。