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.
The first line of the input contains following integers:
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.
For each query print a single integer: the minimum walking time between the locations in minutes.
3 6 2 3 3
1 2 1 3
1 4 3 4
1 2 2 3
1
4
2
Name |
---|