First, we can swap them as needed to assume that \(s _ {x,i}\leq t _ {x,i}\).

Takahashi can minimize his moves by choosing the route as follows:

• Let \((x,y)=(s _ {x,i},s _ {y,i})\) be his initial square.
• While \(x\lt t _ {x,i}\), repeat the following:
  • If \(y\lt L _ {x+1}\), move to square \((x,y+1)\).
  • If \(L _ {x+1}\leq y\leq U _ {x+1}\), move to square \((x+1,y)\).
  • If \(U _ {x+1}\lt y\), move to square \((x,y-1)\).
• While \(y\neq t _ {y,i}\), move to the appropriate position.

This can be justified because making a move toward \(x\) direction as early as possible does not worsen the count, though we do not describe the detailed proof.

Under this algorithm, consider his move from \(x=A-1\) to \(x=B\). For \(y\in\mathbb Z\), when starting the algorithm above from the state where he is at square \((A-1,y)\), let \((B,f _ {\lbrack A,B\rbrack}(y))\) be the first square to reach \(x=B\), and \(g _ {\lbrack A,B\rbrack}(y)\) be the number of moves required. (For convenience, we assume \((A-1,y)\) are all empty.)

Then, there exist \(f=\lbrack f _ L,f _ U\rbrack,g=\lbrack g _ L,g _ U\rbrack\), and \(C\), such that

• \(f _ {\lbrack{A,B}\rbrack}(y)=\operatorname{clamp}(y,f _ L,f _ U)\),
• \(g _ {\lbrack{A,B}\rbrack}(y)=C+\max\lbrace0,g _ L-y,y-g _ U\rbrace\),
• \(f _ L\neq f _ U\vee g _ L\neq g _ U\implies f=g\).

(Here, \(\operatorname{clamp}(x,a,b)\coloneqq\min\lbrace\max\lbrace x,a\rbrace,b\rbrace\).)

Specifically, for \(f _ 1=[f _ {L,1},f _ {U,1}],g _ 1=[g _ {L,1},g _ {U,1}],f _ 2=[f _ {L,2},f _ {U,2}]\), and \(g _ 2=[g _ {L,2},g _ {U,2}]\), the composition can be computed by \[f=[\operatorname{clamp}(f _ {L,1},f _ {L,2},f _ {U,2}),\operatorname{clamp}(f _ {U,1},f _ {L,2},f _ {U,2})]\] and \[g=[\operatorname{clamp}(g _ {L,2},g _ {L,1},g _ {U,1}),\operatorname{clamp}(g _ {U,2},g _ {L,1},g _ {U,1})].\] \(C\) can be found as the number of moves for \(y=g _ L\).

Therefore, merging segments can be done in an \(O(1)\) time.

Since the sequence is not updated, one can use an even faster data structure, but the \(O(N+Q\log N)\) solution using a segment tree is already fast enough.

The following is sample code.

#include <iostream>
#include <vector>
#include <algorithm>
#include <atcoder/segtree>

int main() {
    using namespace std;
    // Structure that manages the cost when entering and exiting the segment [A, B] on x
    // Given the y coordinate on entrance, returns (y coordinate on exit, number of moves).
    struct block{
        unsigned fL, fU;
        unsigned gL, gU;
        unsigned long C;
        pair<unsigned, unsigned long> operator()(unsigned y) const {
            return {clamp(y, fL, fU), C + max(y, gL) - min(y, gU)};
        }
    };
    // Definition of the segment tree
    // The binary operation is merging segments
    using segment_tree = atcoder::segtree<block, [](const block& lhs, const block& rhs) -> block {
        // Rather confusing merge operation
        const auto new_fL{clamp(lhs.fL, rhs.fL, rhs.fU)}, new_fU{clamp(lhs.fU, rhs.fL, rhs.fU)};
        const auto new_gL{clamp(rhs.gL, lhs.gL, lhs.gU)}, new_gU{clamp(rhs.gU, lhs.gL, lhs.gU)};
        const auto new_C{lhs.C + rhs(lhs(new_gU).first).second};
        return {new_fL, new_fU, new_gL, new_gU, new_C};
    }, []{
        // Unit operation opens up everything
        return block{0, 1000000001, 0, 1000000001, 0};
    }>;

    unsigned N;
    cin >> N;
    vector<block> intervals(N);
    for(auto&& [fL, fU, gL, gU, C] : intervals){
        unsigned L, U;
        cin >> L >> U;
        // Construct a value representing a column with [L, U] being empty
        fL = gL = L;
        fU = gU = U;
        C = 1;
    }
    segment_tree seg_tree{intervals};

    unsigned Q;
    cin >> Q;
    for(unsigned i{}; i < Q; ++i){
        unsigned sx, sy, tx, ty;
        cin >> sx >> sy >> tx >> ty;
        if (sx > tx){
            swap(sx, tx);
            swap(sy, ty);
        }
        // When entering [sx, tx] from sy, on which y coordinate it exists with how many moves?
        const auto& [out, cost]{seg_tree.prod(sx, tx)(sy)};
        // Adjust the y coordinate and print it
        cout << max(out, ty) - min(out, ty) + cost << endl;
    }

    return 0;
}