← 返回题目列表

Codeforces · 1020/A

A. SIS 新大楼

中文机器翻译题面 查看原题

您正在查看暑期信息学学校新大楼的平面图。您负责 SIS 后勤工作,因此您非常关心不同地点之间的旅行时间:了解从演讲室到食堂或从健身房到服务器机房需要多长时间非常重要。

该建筑物由 n 座塔楼组成,每座塔楼为 h 层,其中塔楼标记为 1 到 n,楼层标记为 1 到 h。每层 x 上的任意两个相邻塔楼(对于所有 i,有两个塔楼 i 和 i + 1:1 ≤ i ≤ n - 1)之间都有一条通道,其中 a ≤ x ≤ b。在一座塔的任意两层相邻的楼层之间以及任意两座相邻的塔之间步行只需一分钟,前提是该层上有通道。不允许离开大楼。

该图展示了第一个示例。

您已给出 k 对位置 (ta, fa), (tb, fb):塔 ta 的 fa 层和 tb 塔的 fb 层。对于每一对,您需要确定这些位置之间的最短步行时间。

输入

输入的第一行包含以下整数:

- n:建筑物中的塔楼数量(1 ≤ n ≤ 108),
- h:每座塔的层数(1 ≤ h ≤ 108),
- a和b:可以在相邻塔之间移动的最低和最高楼层(1 ≤ a ≤ b ≤ h),
- k:查询总数(1 ≤ k ≤ 104)。

接下来的 k 行包含查询的描述。每个描述由四个整数ta、fa、tb、fb组成(1≤ta,tb≤n,1≤fa,fb≤h)。这对应于查找第 ta 塔的第 fa 层和第 tb 塔的第 fb 层之间的最短行程时间的查询。

输出

对于每个查询,打印一个整数:位置之间的最短步行时间(以分钟为单位)。

示例

输入 #1

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

输出 #1

1
4
2