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

Copy

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

output

Copy

1
4
2
一道特别简单的题
题意：从一个塔的某一层到另一个塔的某一层，需要的最短时间。条件：每上下一层都要一秒，每从一个塔去临近的塔需要一秒，每个塔去临近的塔只有a-b层有通道去。 
思路：分类讨论一下。 
1、当出发地和目的地是同一个塔:abs(fa-fb) 
2.1、当出发地和目的地不同塔：但是有一个在有通道范围内，或者两者都不在范围内但一个<=a一个>=b:abs(ta-tb)+abs(fa-fb) 
2.2、当出发和目的地楼层都<=a：abs(ta-tb)+abs(fa-a)+abs(fb-a)  2.3、当出发地和目的地楼层都>=b:abs(ta-tb)+abs(fa-b)+abs(fb-b)
此人的思维：https://blog.csdn.net/miranda_ymz/article/details/81603271
但是我不喜欢此人的代码。

if(ta==tb)
cout<<abs(fa-fb)<<endl;

这是第一部分“当出发地和目的地是同一个塔”

else
{
if(fa>=b&&fb>=b)
cout<<abs(ta-tb)+(fb-b)+(fa-b)<<endl;
else if(fa<=a&&fb<=a)
cout<<abs(ta-tb)+(a-fa)+(a-fb)<<endl;
else
cout<<abs(ta-tb)+abs(fa-fb)<<endl;
}

这是第二部分，你只需要控制先判断同在b之上和同在a之下，剩余的就是一个大于b或者小于a，另一个在a和b之间。（不用那么多的判断）

上代码

#include
#include
#include
using namespace std;
int main()
{
int n,h,a,b,k;
cin>>n>>h>>a>>b>>k;
while(k--)
{
int ta,tb,fa,fb;
cin>>ta>>fa>>tb>>fb;
if(ta==tb)
cout<=b&&fb>=b)
cout<<abs(ta-tb)+(fb-b)+(fa-b)<<endl;
else if(fa<=a&&fb<=a)
cout<<abs(ta-tb)+(a-fa)+(a-fb)<<endl;
else
cout<<abs(ta-tb)+abs(fa-fb)<<endl;
}
}
return ;
}