每天有很多趟货运列车从基尔尼斯星球出发。该星球上的一天由 $$$h$$$ 小时组成,每一小时由 $$$m$$$ 分钟组成,其中 $$$m$$$ 是偶数。目前,有$$$n$$$货运列车,并且每天在同一时间出发:$$$i$$$第$$$h_i$$$小时和$$$m_i$$$分钟出发。
政府还决定增加客运有轨电车:他们计划增加每半小时一班的常规有轨电车服务。这意味着当天的第一趟有轨电车必须在 $$$0$$$ 小时和 $$$t$$$ 分钟出发,其中 $$$0 \le t < {m \over 2}$$$,第二趟有轨电车在第一趟电车之后 $$$m \over 2$$$ 分钟出发,依此类推。这个时间表每小时正好允许两趟客运电车,这是一个很大的进步。
为了让乘客安全登上电车,电车必须提前 $$$k$$$ 分钟到达。在乘客登上有轨电车期间,任何货运列车都不能离开地球。然而,货运列车可以在登车开始的那一刻出发,也可以在客运电车出发的那一刻出发。请注意,如果第一趟客运电车在 $$$0$$$ 小时和 $$$t$$$ 分钟出发,其中 $$$t < k$$$,则货运列车不能在当天的最后 $$$k - t$$$ 分钟内出发。
客运电车正确运行方式示意图。这里$$$h=2$$$(因此客运电车的车数为$$$2h=4$$$),货运列车的车数为$$$n=6$$$。客运电车标记为红色(注意它们之间的间距是相同的)。货运列车标记为蓝色。每趟客运电车之前长度为 $$$k$$$ 的时间段以红色突出显示。请注意,这些路段内没有货运列车。
不幸的是,如果不取消部分货运列车,可能就无法满足政府的要求。请帮助政府找到 $$$t$$$ 的最佳值,以最大限度地减少取消货运列车的数量,以防所有客运电车均按时间表出发。
输入
输入的第一行包含四个整数 $$$n$$$, $$$h$$$, $$$m$$$, $$$k$$$ ($$$1 \le n \le 100\,000$$$, $$$1 \le h \le 10^9$$$, $$$2 \le m \le 10^9$$$, $$$m$$$是偶数,$$$1 \le k \le {m \over 2}$$$) - 每天货运列车的数量、地球上的小时数和分钟数以及每辆客运电车的登车时间。
$$$n$$$ 行,每行包含两个整数 $$$h_i$$$ 和 $$$m_i$$$ ($$$0 \le h_i < h$$$, $$$0 \le m_i < m$$$) — 第 $$$i$$$ 货运列车出发的时间。保证没有货运列车同时出发。
输出
输出的第一行应包含两个整数:需要取消的列车的最小数量,以及最佳出发时间$$$t$$$。第二行输出应包含需要取消的货运列车。
示例
输入 #1
2 24 60 15 16 0 17 15
输出 #1
0 0
输入 #2
2 24 60 16 16 0 17 15
输出 #2
1 0 2
注意
在示例的第一个测试用例中,第一辆有轨电车可以在 0 小时 0 分钟出发。那么16小时00分的货运列车可以与客运电车同时发车,17小时15分的货运列车可以与即将上车的客运电车开始上车同时出发。
在示例的第二个测试用例中,不可能在不取消任何货运列车的情况下设计客运电车时刻表:如果 $$$t \in [1, 15]$$$,则 16 小时 0 分钟的货运列车无法出发(因为上车时间为 16 分钟)。若$$$t = 0$$$或$$$t \in [16, 29]$$$,则17小时15分出发的货运列车无法发车。然而,如果第二趟货运列车取消,则可以选择$$$t = 0$$$。另一种可能的选择是取消第一趟列车并选择 $$$t = 13$$$。