You are looking at the floor plan of the Summer Informatics School's new building. You were tasked with SIS logistics, so you really care about travel time between different locations: it is important to know how long it would take to get from the lecture room to the canteen, or from the gym to the server room.
The building consists of _n_ towers, _h_ floors each, where the towers are labeled from 1 to _n_, the floors are labeled from 1 to _h_. There is a passage between any two adjacent towers (two towers _i_ and _i_ + 1 for all _i_: 1 ≤ _i_ ≤ _n_ - 1) on every floor _x_, where _a_ ≤ _x_ ≤ _b_. It takes exactly one minute to walk between any two adjacent floors of a tower, as well as between any two adjacent towers, provided that there is a passage on that floor. It is not permitted to leave the building.
<center>The picture illustrates the first example.
</center>You have given _k_ pairs of locations (_t__a_, _f__a_), (_t__b_, _f__b_): floor _f__a_ of tower _t__a_ and floor _f__b_ of tower _t__b_. For each pair you need to determine the minimum walking time between these locations.
## Input
The first line of the input contains following integers:
* _n_: the number of towers in the building (1 ≤ _n_ ≤ 108),
* _h_: the number of floors in each tower (1 ≤ _h_ ≤ 108),
* _a_ and _b_: the lowest and highest floor where it's possible to move between adjacent towers (1 ≤ _a_ ≤ _b_ ≤ _h_),
* _k_: total number of queries (1 ≤ _k_ ≤ 104).
Next _k_ lines contain description of the queries. Each description consists of four integers _t__a_, _f__a_, _t__b_, _f__b_ (1 ≤ _t__a_, _t__b_ ≤ _n_, 1 ≤ _f__a_, _f__b_ ≤ _h_). This corresponds to a query to find the minimum travel time between _f__a_\-th floor of the _t__a_\-th tower and _f__b_\-th floor of the _t__b_\-th tower.
## Output
For each query print a single integer: the minimum walking time between the locations in minutes.
[samples]
你正在查看夏季信息学学校新大楼的平面图。你负责 SIS 的后勤工作，因此非常关心不同地点之间的通行时间：知道从教室到食堂，或从体育馆到服务器机房需要多长时间非常重要。
该大楼由 #cf_span[n] 座塔楼组成，每座塔楼有 #cf_span[h] 层，塔楼编号从 #cf_span[1] 到 #cf_span[n]，楼层编号从 #cf_span[1] 到 #cf_span[h]。在每一层 #cf_span[x]（其中 #cf_span[a ≤ x ≤ b]）上，任意两座相邻塔楼（即对所有 #cf_span[i]：#cf_span[1 ≤ i ≤ n - 1]，塔楼 #cf_span[i] 和 #cf_span[i + 1]）之间都有通道。在一座塔楼内上下相邻楼层，或在有通道的楼层上在相邻塔楼间移动，均恰好需要一分钟。不允许离开大楼。
#cf_span(class=[tex-font-size-small], body=[该图说明了第一个示例。])
你获得了 #cf_span[k] 对位置 #cf_span[(ta, fa)] 和 #cf_span[(tb, fb)]：塔楼 #cf_span[ta] 的第 #cf_span[fa] 层和塔楼 #cf_span[tb] 的第 #cf_span[fb] 层。对于每一对位置，你需要确定这两点之间的最短步行时间。
输入的第一行包含以下整数：
接下来的 #cf_span[k] 行包含每个查询的描述。每个描述由四个整数 #cf_span[ta], #cf_span[fa], #cf_span[tb], #cf_span[fb] 组成（#cf_span[1 ≤ ta, tb ≤ n], #cf_span[1 ≤ fa, fb ≤ h]），表示查询从塔楼 #cf_span[ta] 的第 #cf_span[fa] 层到塔楼 #cf_span[tb] 的第 #cf_span[fb] 层的最短通行时间。
对于每个查询，输出一个整数：两点之间的最短步行时间（单位：分钟）。
## Input
输入的第一行包含以下整数：#cf_span[n]（大楼中的塔楼数量，#cf_span[1 ≤ n ≤ 10^8]）、#cf_span[h]（每座塔楼的楼层数，#cf_span[1 ≤ h ≤ 10^8]）、#cf_span[a] 和 #cf_span[b]（允许在相邻塔楼间通行的最低和最高楼层，#cf_span[1 ≤ a ≤ b ≤ h]）、#cf_span[k]（查询总数，#cf_span[1 ≤ k ≤ 10^4]）。接下来的 #cf_span[k] 行包含每个查询的描述。每个描述由四个整数 #cf_span[ta], #cf_span[fa], #cf_span[tb], #cf_span[fb]（#cf_span[1 ≤ ta, tb ≤ n], #cf_span[1 ≤ fa, fb ≤ h]）组成，表示查询从塔楼 #cf_span[ta] 的第 #cf_span[fa] 层到塔楼 #cf_span[tb] 的第 #cf_span[fb] 层的最短通行时间。
## Output
对于每个查询，输出一个整数：两点之间的最短步行时间（单位：分钟）。
[samples]
**Definitions**
Let $ n, h, a, b, k \in \mathbb{Z}^+ $ be given constants:
- $ n $: number of towers, labeled $ 1 $ to $ n $.
- $ h $: number of floors per tower, labeled $ 1 $ to $ h $.
- $ [a, b] \subseteq [1, h] $: the range of floors on which horizontal passages between adjacent towers exist.
Let $ Q = \{(t_a, f_a, t_b, f_b)_i \mid i \in \{1, \dots, k\}\} $ be the set of $ k $ queries, where each query specifies:
- Start: floor $ f_a $ of tower $ t_a $,
- End: floor $ f_b $ of tower $ t_b $.
**Constraints**
1. $ 1 \leq t_a, t_b \leq n $
2. $ 1 \leq f_a, f_b \leq h $
3. $ 1 \leq a \leq b \leq h $
4. Movement is allowed:
- Vertically within a tower: 1 minute per floor change.
- Horizontally between adjacent towers $ i $ and $ i+1 $: 1 minute, **only if** the current floor $ x \in [a, b] $.
- No movement outside the building.
**Objective**
For each query $ (t_a, f_a, t_b, f_b) \in Q $, compute the minimum travel time $ T $ in minutes from $ (t_a, f_a) $ to $ (t_b, f_b) $, where:
$$
T = \min_{\substack{x \in [a,b] \cup \{f_a, f_b\} \\ \text{if } t_a \ne t_b}} \left( |f_a - x| + |t_a - t_b| + |x - f_b| \right)
$$
if $ t_a \ne t_b $, and
$$
T = |f_a - f_b|
$$
if $ t_a = t_b $.
Equivalently, the solution is:
$$
T = |f_a - f_b| + |t_a - t_b| \quad \text{if } \min(f_a, f_b) \geq a \text{ and } \max(f_a, f_b) \leq b
$$
otherwise,
$$
T = |f_a - f_b| + |t_a - t_b| + 2 \cdot \min\left( \max(a - \min(f_a, f_b), 0), \max(\max(f_a, f_b) - b, 0) \right)
$$
But more cleanly:
Let $ \Delta_t = |t_a - t_b| $, $ \Delta_f = |f_a - f_b| $.
Then:
$$
T = \Delta_f + \Delta_t + 2 \cdot \max\left(0, a - \min(f_a, f_b), \max(f_a, f_b) - b \right)
$$
**Wait — correction:** The correct minimal path is:
If $ t_a = t_b $:
$$
T = |f_a - f_b|
$$
If $ t_a \ne t_b $:
$$
T = \min_{x \in \{a, b, f_a, f_b\} \cap [a,b]} \left( |f_a - x| + |t_a - t_b| + |x - f_b| \right)
$$
But since $ |f_a - x| + |x - f_b| \geq |f_a - f_b| $, and equality holds when $ x \in [\min(f_a,f_b), \max(f_a,f_b)] $, we can write:
Define $ L = \min(f_a, f_b) $, $ R = \max(f_a, f_b) $.
Then:
- If $ [L, R] \cap [a, b] \ne \emptyset $, then $ T = |f_a - f_b| + |t_a - t_b| $
- Else, let $ d = \min(|L - b|, |R - a|) $, then $ T = |f_a - f_b| + |t_a - t_b| + 2d $
Thus, formally:
Let $ \Delta_t = |t_a - t_b| $, $ \Delta_f = |f_a - f_b| $,
$ L = \min(f_a, f_b) $, $ R = \max(f_a, f_b) $.
Then:
$$
T =
\begin{cases}
\Delta_f & \text{if } t_a = t_b \\
\Delta_f + \Delta_t & \text{if } [L, R] \cap [a, b] \ne \emptyset \\
\Delta_f + \Delta_t + 2 \cdot \min(b - L, R - a) & \text{otherwise}
\end{cases}
$$
But note: if $ R < a $, then $ \min(b - L, R - a) = R - a $ is negative — so we must take **positive** detour:
Actually, the detour cost is:
- If $ R < a $: must go up to $ a $, so detour = $ (a - L) + (a - R) = 2a - L - R $
- If $ L > b $: must go down to $ b $, so detour = $ (L - b) + (R - b) = L + R - 2b $
So:
$$
\text{detour} =
\begin{cases}
2(a - R) & \text{if } R < a \\
2(L - b) & \text{if } L > b \\
0 & \text{otherwise}
\end{cases}
$$
Thus:
$$
T = |f_a - f_b| + |t_a - t_b| +
\begin{cases}
2(a - \max(f_a, f_b)) & \text{if } \max(f_a, f_b) < a \\
2(\min(f_a, f_b) - b) & \text{if } \min(f_a, f_b) > b \\
0 & \text{otherwise}
\end{cases}
$$
**Final Formal Objective**
For each query $ (t_a, f_a, t_b, f_b) $:
Let $ \Delta_t = |t_a - t_b| $, $ \Delta_f = |f_a - f_b| $,
$ L = \min(f_a, f_b) $, $ R = \max(f_a, f_b) $.
Then:
$$
T = \Delta_f + \Delta_t +
\begin{cases}
2(a - R) & \text{if } R < a \\
2(L - b) & \text{if } L > b \\
0 & \text{otherwise}
\end{cases}
$$