高桥君在网格上

题目描述

平面上有无限多个格子。对于每一对整数 $(x,y)$，都有一个对应的格子，我们称之为格子 $(x,y)$。

每个格子要么是空地，要么是墙壁。

给定两个长度为 $N$ 的正整数序列 $L=(L_1,L_2,\dotsc,L_N)$ 和 $U=(U_1,U_2,\dotsc,U_N)$。其中，$L_i$ 和 $U_i$ 满足 $1\leq L_i\leq U_i\leq10^9$（$i=1,2,\ldots,N$）。

所有格子 $(x,y)\ (1\leq x\leq N,\ L_x\leq y\leq U_x)$ 都是空地，其余格子都是墙壁。

当高桥君位于空地 $(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})$ 所需的最少操作次数。对于每个询问，保证给定的两个格子都是空地。

输入格式

输入按以下格式从标准输入给出。

$N$
$L_1$ $U_1$
$L_2$ $U_2$
$\vdots$
$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}$
$\vdots$
$s_{x,Q}$ $s_{y,Q}$ $t_{x,Q}$ $t_{y,Q}$

输出格式

输出 $Q$ 行。第 $i$ 行（$1\leq i\leq Q$）输出第 $i$ 个询问的答案。

样例

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

10
3
14

给定的格子如下所示。

对于第一个询问，例如高桥君可以按如下方式用十次操作从格子 $(1,4)$ 移动到格子 $(6,3)$。

从格子 $(1,4)$ 移动到格子 $(6,3)$ 不可能在九次或更少的操作内完成，所以输出 $10$。

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

6000000005

注意，输出值可能无法用 $32$ 位整数表示。

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

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

数据范围

• $1\leq N\leq2\times10^5$
• $1\leq L_i\leq U_i\leq10^9\ (1\leq i\leq N)$
• $[L_i,U_i]\cap[L_{i+1},U_{i+1}]\neq\emptyset\ (1\leq i\lt N)$
• $1\leq Q\leq2\times10^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)$
• 所有输入值均为整数