Score : $575$ points

问题陈述

平面上有无限多的单元格。对于每一对整数 $(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})$ 所需的最小动作数。对于每个查询，保证给定的两个单元格都是空单元格。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

There are infinitely many cells on a plane. For every pair of integers $(x,y)$, there is a corresponding cell, which we will call cell $(x,y)$.

Each cell is either an empty cell or a wall cell.
You are given two sequences of positive integers of length $N$: $L=(L _ 1,L _ 2,\dotsc,L _ N)$ and $U=(U _ 1,U _ 2,\dotsc,U _ N)$. Here, $L _ i$ and $U _ i$ satisfy $1\leq L _ i\leq U _ i\leq10 ^ 9$ for $i=1,2,\ldots,N$.
All cells $(x,y)\ (1\leq x\leq N,L _ x\leq y\leq U _ x)$ are empty cells, and all other cells are wall cells.

When Takahashi is at an empty cell $(x,y)$, he can perform one of the following actions.

• If cell $(x+1,y)$ is an empty cell, move to cell $(x+1,y)$.
• If cell $(x-1,y)$ is an empty cell, move to cell $(x-1,y)$.
• If cell $(x,y+1)$ is an empty cell, move to cell $(x,y+1)$.
• If cell $(x,y-1)$ is an empty cell, move to cell $(x,y-1)$.

It is guaranteed that he can travel between any two empty cells by repeating his actions.

Answer $Q$ queries in the following format.

For the $i$-th query $(1\leq i\leq Q)$, you are given a quadruple of integers $(s _ {x,i},s _ {y,i},t _ {x,i},t _ {y,i})$. Find the minimum number of actions required for Takahashi to move from cell $(s _ {x,i},s _ {y,i})$ to cell $(t _ {x,i},t _ {y,i})$. For each query, it is guaranteed that the given two cells are empty cells.

Constraints

• $1\leq N\leq2\times10 ^ 5$
• $1\leq L _ i\leq U _ i\leq10 ^ 9\ (1\leq i\leq N)$
• $\lbrack L _ i,U _ i\rbrack\cap\lbrack L _ {i+1},U _ {i+1}\rbrack\neq\emptyset\ (1\leq i\lt N)$
• $1\leq Q\leq2\times10 ^ 5$
• $1\leq s _ {x,i}\leq N$ and $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$ and $L _ {t _ {x,i}}\leq t _ {y,i}\leq U _ {t _ {x,i}}\ (1\leq i\leq Q)$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$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}$

Output

Print $Q$ lines. The $i$-th line $(1\leq i\leq Q)$ should contain the answer to the $i$-th query.

Sample Input 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

Sample Output 1

10
3
14

The given cells are as follows.

For the first query, for example, Takahashi can move from cell $(1,4)$ to cell $(6,3)$ in ten actions as follows.

It is impossible to move from cell $(1,4)$ to cell $(6,3)$ in nine or fewer actions, so print $10$.

Sample Input 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

Sample Output 2

6000000005

Note that the output value may not fit in a $32$-bit integer.

Sample Input 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

Sample Output 3

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