AT_abc365_f.[ABC365F] Takahashi on Grid

平面上有无限多个格子。对于所有整数二元组 $(x, y)$，都存在一个对应的格子，称为格子 $(x, y)$。

每个格子要么是空格子，要么是墙格子。
给定长度为 $N$ 的正整数序列 $L = (L_1, L_2, \dotsc, L_N)$，$U = (U_1, U_2, \dotsc, U_N)$。其中，对于 $i = 1, 2, \ldots, N$，有 $1 \leq L_i \leq U_i \leq 10^9$。
满足 $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})$ 所需的最小操作次数。保证每个询问给定的两个格子都是空格子。

输入按以下格式从标准输入读入。

$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$ 行输出第 $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)$
• 输入均为整数

样例解释 1

给定的格子如下图所示。

对于第 $1$ 个询问，例如可以如下移动，从格子 $(1,4)$ 经过 $10$ 次操作到达格子 $(6,3)$。

无法用 $9$ 次或更少的操作从 $(1,4)$ 到 $(6,3)$，因此应输出 $10$。

样例解释 2

注意输出的值可能超出 $32$ 位整数范围。

由 ChatGPT 4.1 翻译