A - New Building for SIS
阅读原文时间:2023年07月10日阅读:1

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 ≤ 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.

Example

Input

3 6 2 3 3
1 2 1 3
1 4 3 4
1 2 2 3

Output

1
4
2
题意:一个人在楼之间穿梭,不同楼层之间通过的楼梯给出范围,穿梭楼层以及不同楼之间的时间为1min,求从目标地到最后的地方需要最少的时间
题解:该题有个大坑-----此人可能在一栋楼上,那么不需要考虑楼层之间的问题;(万幸吃个零食想了出来orz)
那么情况分为两种:
一种是一栋楼,,直接做差即可;
第二种是不同楼,画图可知----走弯路情况只有两种(一个是目的地和出发的都在规定楼层上面,一个是在规定楼层下面),其余情况做差就可
注意:做差时加绝对值
ac代码
#include
#include
#include
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(fahig&&fb>hig)
                ans+=(fa-hig+fb-hig);
            else
                ans+=abs(fa-fb);
        }
        cout<<ans<<endl;
    }
    return 0;
}

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章