New Building for SIS

1000ms

262144K

Description:

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.

$\text{[math]}$

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.

Sample Input:

Sample Output:

1
4
2

Informação

Provedor Codeforces

Código CF1020A