【CodeForces - 1020A】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 (ta, fa), (tb, fb): floor fa of tower ta and floor fb of tower tb. 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 ta, fa, tb, fb (1 ≤ ta, tb ≤ n, 1 ≤ fa, fb ≤ h). This corresponds to a query to find the minimum travel time between fa-th floor of the ta-th tower and fb-th floor of the tb-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

题目大意：

第一行n <= 10^8 代表楼房个数 第二行h <= 10^8 代表楼房高度 然后 a，b 两个整数代表第a楼到第b楼有空中电梯 有电梯的楼层，相邻两栋楼移动一步可以到达，每个楼的相邻两个楼层移动一步可以到达 然后 一个整数k <= 10^4 然后k行每行有ta fa tb fb 分别是 a b两个地方的楼号 楼层号 输出最少移动步数

解题报告：

   直接模拟就行了，注意特殊样例，比如在同一个楼的不同层里，比如在不同楼的同一层里。

AC代码：

#include<bits/stdc++.h> #define ll long long using namespace std; int n,h,a,b,k; int main() {cin>>n>>h>>a>>b>>k;int t1,f1,t2,f2;int cur;ll ans = 0;while(k--) {ans = 0;scanf("%d%d%d%d",&t1,&f1,&t2,&f2);if(t1 == t2) {printf("%d\n",abs(f2-f1));continue;}if(t1 > t2) {swap(t1,t2);}if(f1>f2) swap(f1,f2);if(f1 <= a) ans += (a-f1),cur = a;else if(f1 >= b) ans += (f1 - b), cur = b;else cur = f1;ans += (t2-t1);ans += abs(cur - f2);printf("%lld\n",ans);}return 0 ; }

 

总结

以上是生活随笔为你收集整理的【CodeForces - 1020A】New Building for SIS（模拟）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。