题目描述

小奥尔菲斯生活在欧利蒂丝庄园。庄园可以看成一个平面，我们将这个平面划分为单元格。每对整数 $(x,y)$ 对应一个单元格，我们称这个单元格为单元格 $(x,y)$。每个单元格要么是空地，要么是墙体。

现在给出两个长为 $n$ 的正整数序列：$l_1,l_2,\dots,l_n$ 和 $u_1,u_2,\dots,u_n$。其中对任意的 $i=1,2,\dots,n$ 都有 $l_i\le u_i$。所有的单元格 $(x,y)\ (1\le x\le n,l_x\le y\le 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$ 次询问，给出四个正整数 $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$。

接下来的 $n$ 行每行包含两个正整数 $l_i,u_i$。

输入的第 $n+2$ 行包含一个正整数 $q$。

接下来的 $q$ 行每行包含四个正整数 $s_{x,i},s_{y,i},t_{x,i},t_{y,i}$。

输出格式

对于每次询问输出一行一个整数表示答案。