Перед вами на столе план нового здания, где планируется проводить Летнюю Компьютерную Школу. Вы работаете над логистикой для ЛКШ, поэтому вам интересно, как быстро можно добраться между разными важными точками: например, сколько минут идти от аудитории до столовой или от спортзала до серверной.
В здании n башен, в каждой башне по h этажей. Башни пронумерованы от 1 до n, этажи в каждой башне пронумерованы от 1 до h. Между соседними башнями (то есть башнями с номерами i и i + 1 для всех i: 1 ≤ i ≤ n - 1) есть переходы на всех этажах x: a ≤ x ≤ b. Подняться или спуститься на один этаж внутри башни можно ровно за одну минуту. Также за одну минуту можно перейти между соседними башнями, если на вашем этаже есть переход. Покидать здание не разрешается.
Рисунок иллюстрирует первый пример.
У вас есть список из k пар мест (ta, fa), (tb, fb): этаж fa башни ta и этаж fb башни tb. Для каждой пары мест требуется вычислить минимальное время перемещения между ними.
В первой строке ввода записаны целые числа:
- n: количество башен в здании (1 ≤ n ≤ 108),
- h: количество этажей в башнях (1 ≤ h ≤ 108),
- a and b: минимальный и максимальный этаж, где есть переходы между соседними башнями (1 ≤ a ≤ b ≤ h),
- k: количество запросов минимального времени перемещения (1 ≤ k ≤ 104).
В следующих k строках записано по четыре целых числа: ta, fa, tb, fb (1 ≤ ta, tb ≤ n, 1 ≤ fa, fb ≤ h). Эти числа соответствуют запросу на поиск минимального времени перемещения между fa-м этажом ta-й башни и fb-м этажом tb-й башни.
Для каждого запроса выведите одно целое число на отдельной строке: минимальное время перемещения.
3 6 2 3 3
1 2 1 3
1 4 3 4
1 2 2 3
1
4
2
