You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

在一个无限平面上有无数个单元格。对于每一对整数 $x, y$，都有一个对应的单元格，称为单元格 $x, y$。

每个单元格要么是空单元格，要么是墙单元格。你将得到两个长度为 $N$ 的正整数序列：$L = (L_1, L_2, \ldots, L_N)$ 和 $U = (U_1, U_2, \ldots, U_N)$。这里，$L_i$ 和 $U_i$ 满足 $1 \leq L_i \leq U_i \leq 10^9$（对于 $i = 1, 2, \ldots, N$）。所有满足 $1 \leq x \leq N, L_x \leq y \leq U_x$ 的单元格 $(x, y)$ 是空单元格，其他单元格是墙单元格。

当高桥在一个空单元格 $(x, y)$ 时，他可以执行以下操作之一：

• 如果单元格 $(x+1, y)$ 是空单元格，移动到单元格 $(x+1, y)$。
• 如果单元格 $(x-1, y)$ 是空单元格，移动到单元格 $(x-1, y)$。
• 如果单元格 $(x, y+1)$ 是空单元格，移动到单元格 $(x, y+1)$。
• 如果单元格 $(x, y-1)$ 是空单元格，移动到单元格 $(x, y-1)$。

保证他可以通过重复操作在任意两个空单元格之间旅行。

回答 $Q$ 个查询，格式如下：

对于第 $i$ 个查询 $(1 \leq i \leq Q)$，给定四个整数 $(s_{x,i}, s_{y,i}, t_{x,i}, t_{y,i})$。求高桥从单元格 $(s_{x,i}, s_{y,i})$ 移动到单元格 $(t_{x,i}, t_{y,i})$ 所需的最小操作次数。对于每个查询，保证给定的两个单元格都是空单元格。

约束条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq L_i \leq U_i \leq 10^9$ （$1 \leq i \leq N$）
• $[L_i, U_i] \cap [L_{i+1}, U_i+1] \neq \emptyset$ （$1 \leq i < N$）
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq s_{x,i} \leq N$ 且 $L_{s_{x,i}} \leq s_{y,i} \leq U_{s_{x,i}}$ （$1 \leq i \leq Q$）
• $1 \leq t_{x,i} \leq N$ 且 $L_{t_{x,i}} \leq t_{y,i} \leq U_{t_{x,i}}$ （$1 \leq i \leq Q$）
• 所有输入值都是整数。

输入格式

输入从标准输入给出，格式如下：

N
L_1 U_1
L_2 U_2
⋮
L_N U_N
Q
s_{x,1} s_{y,1} t_{x,1} t_{y,1}
s_{x,2} s_{y,2} t_{x,2} t_{y,2}
⋮
s_{x,Q} s_{y,Q} t_{x,Q} t_{y,Q}

输出格式

输出 $Q$ 行。第 $i$ 行 $(1 \leq i \leq Q)$ 应包含第 $i$ 个查询的答案。

样例 #1

样例输入 #1

7
1 5
3 3
1 3
1 1
1 4
2 4
3 5
3
1 4 6 3
1 4 1 1
7 5 1 5

样例输出 #1

10
3
14

解释

对于第一个查询，

例如，高桥可以通过以下操作从单元格 $(1,4)$ 移动到单元格 $(6,3)$，共需 $10$ 次操作。

样例 #2

样例输入 #2

12
1 1000000000
1000000000 1000000000
1 1000000000
1 1
1 1000000000
1000000000 1000000000
1 1000000000
1 1
1 1000000000
1000000000 1000000000
1 1000000000
1 1
1
1 1 12 1

样例输出 #2

6000000005

解释

注意输出值可能不适合 $32$ 位整数。

样例 #3

样例输入 #3

10
1694 7483
3396 5566
2567 6970
1255 3799
2657 3195
3158 8007
3368 8266
1447 6359
5365 8614
3141 7245
15
3 3911 6 4694
7 5850 10 4641
1 5586 6 4808
2 3401 8 2676
3 3023 6 6923
8 4082 3 6531
6 3216 7 6282
8 5121 8 3459
8 4388 1 6339
6 6001 3 6771
10 5873 8 5780
1 6512 6 6832
8 5345 7 4975
10 4010 8 2355
7 5837 9 6279

样例输出 #3

2218
1212
4009
1077
3903
4228
3067
1662
4344
6385
95
6959
371
4367
444