A - New Building for SIS

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.

The picture illustrates the first example.

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 ≤ 10⁸),
h: the number of floors in each tower (1 ≤ h ≤ 10⁸),
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 ≤ 10⁴).

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.

Example

Input

Output

1
4
2
题意：一个人在楼之间穿梭，不同楼层之间通过的楼梯给出范围，穿梭楼层以及不同楼之间的时间为1min，求从目标地到最后的地方需要最少的时间
题解：该题有个大坑-----此人可能在一栋楼上，那么不需要考虑楼层之间的问题；（万幸吃个零食想了出来orz）
    那么情况分为两种：
一种是一栋楼，，直接做差即可；
第二种是不同楼，画图可知----走弯路情况只有两种（一个是目的地和出发的都在规定楼层上面，一个是在规定楼层下面），其余情况做差就可
注意：做差时加绝对值
ac代码
#include<iostream>
#include<cmath>
#include<cstdlib>
using namespace std;
int n,h,low,hig,k;
int main()
{
    long long ans;
    int ta,fa,tb,fb;
    cin>>n>>h>>low>>hig>>k;
    for(int i=1; i<=k; i++)
    {
        cin>>ta>>fa>>tb>>fb;
        if(ta==tb)
            ans=abs(fa-fb);
        else
        {
            ans=abs(tb-ta);
            if(fa<low&&fb<low)
                ans+=(low-fa+low-fb);
            else if(fa>hig&&fb>hig)
                ans+=(fa-hig+fb-hig);
            else
                ans+=abs(fa-fb);
        }
        cout<<ans<<endl;
    }
    return 0;
}

巴特西

A - New Building for SIS

最新文章

热门文章