Problem Description

There are an infinite number of squares on a plane. For every pair of integers $ (x,y) $, there exists one corresponding square, which we call square $ (x,y) $.

Each square is either an empty square or a wall square.
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)$. For $i=1,2,\ldots,N$, $ L_i $ and $ U_i $ satisfy $1\leq L_i\leq U_i\leq10^9$.
All squares $ (x,y) $ where $1\leq x\leq N$ and $L_x\leq y\leq U_x$ are empty squares, and all other squares are wall squares.

When Takahashi is on an empty square $ (x,y) $, he can perform one of the following actions:

• Move to square $ (x+1,y) $ if it is an empty square.
• Move to square $ (x-1,y) $ if it is an empty square.
• Move to square $ (x,y+1) $ if it is an empty square.
• Move to square $ (x,y-1) $ if it is an empty square.

It is guaranteed that any two empty squares can be reached from one another by repeatedly performing actions.

Answer $ Q $ queries of the following form:

In the $ i $-th query $(1\leq i\leq Q)$, a quadruple of integers $ (s_{x,i},s_{y,i},t_{x,i},t_{y,i}) $ is given. Determine the minimum number of actions required for Takahashi to move from square $ (s_{x,i},s_{y,i}) $ to square $ (t_{x,i},t_{y,i}) $. It is guaranteed that both squares given in each query are empty squares.

Input Format

The input is given from the 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 Format

Output $ Q $ lines. On the $ i $-th line $(1\leq i\leq Q)$, output the answer to the $ i $-th query.

Sample Input and Output

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

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

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

Notes/Hints

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.

Sample Explanation 1

The given squares are as follows: Since it is not possible to move from square $ (1,4) $ to square $ (6,3) $ in $ 9 $ or fewer actions, output $ 10 $.

Sample Explanation 2

Note that the value to be output may not fit into a $ 32 $-bit integer.

见题面 Input 部分

见题面 Output 部分