CF1379D.New Passenger Trams

There are many freight trains departing from Kirnes planet every day. One day on that planet consists of $h$ hours, and each hour consists of $m$ minutes, where $m$ is an even number. Currently, there are $n$ freight trains, and they depart every day at the same time: $i$-th train departs at $h_i$ hours and $m_i$ minutes.

The government decided to add passenger trams as well: they plan to add a regular tram service with half-hour intervals. It means that the first tram of the day must depart at $0$ hours and $t$ minutes, where $0 \le t \lt {m \over 2}$, the second tram departs $m \over 2$ minutes after the first one and so on. This schedule allows exactly two passenger trams per hour, which is a great improvement.

To allow passengers to board the tram safely, the tram must arrive $k$ minutes before. During the time when passengers are boarding the tram, no freight train can depart from the planet. However, freight trains are allowed to depart at the very moment when the boarding starts, as well as at the moment when the passenger tram departs. Note that, if the first passenger tram departs at $0$ hours and $t$ minutes, where $t \lt k$, then the freight trains can not depart during the last $k - t$ minutes of the day.

A schematic picture of the correct way to run passenger trams. Here $h=2$ (therefore, the number of passenger trams is $2h=4$), the number of freight trains is $n=6$. The passenger trams are marked in red (note that the spaces between them are the same). The freight trains are marked in blue. Time segments of length $k$ before each passenger tram are highlighted in red. Note that there are no freight trains inside these segments.

Unfortunately, it might not be possible to satisfy the requirements of the government without canceling some of the freight trains. Please help the government find the optimal value of $t$ to minimize the number of canceled freight trains in case all passenger trams depart according to schedule.

每天都有许多货运列车从基尔内斯星球出发。该星球上的一天由 $h$ 小时组成，每小时由 $m$ 分钟组成，其中 $m$ 为偶数。目前共有 $n$ 列货运列车，它们每天均在同一时刻出发：第 $i$ 列列车在 $h_i$ 小时 $m_i$ 分钟出发。

政府决定增设客运有轨电车服务：计划开通一种间隔为半小时的常规电车服务。这意味着当天首班电车必须在 $0$ 小时 $t$ 分钟出发，其中 $0 \le t \lt {m \over 2}$；第二班电车在首班车出发后 ${m \over 2}$ 分钟出发，依此类推。该时刻表确保每小时恰好有两班客运电车，是一项重大改进。

为保障乘客安全登车，电车须提前 $k$ 分钟抵达车站。在乘客登车期间，星球上不得有任何货运列车出发。但允许货运列车在乘客开始登车的确切时刻，以及客运电车出发的确切时刻出发。注意：若首班客运电车在 $0$ 小时 $t$ 分钟出发，且 $t \lt k$，则当天最后 $k - t$ 分钟内禁止货运列车出发。

客运电车正确运行方式的示意图。此处 $h=2$（因此客运电车总数为 $2h=4$），货运列车数量为 $n=6$。客运电车以红色标出（注意其时间间隔相等），货运列车以蓝色标出。每班客运电车出发前长度为 $k$ 的时间段以红色高亮显示。注意：这些高亮时间段内没有货运列车出发。

遗憾的是，在不取消部分货运列车的情况下，可能无法满足政府的要求。请协助政府确定最优的 $t$ 值，使得在所有客运电车均按时刻表运行的前提下，被取消的货运列车数量最少。

The first line of input contains four integers $n$, $h$, $m$, $k$ ($1 \le n \le 100\,000$, $1 \le h \le 10^9$, $2 \le m \le 10^9$, $m$ is even, $1 \le k \le {m \over 2}$) — the number of freight trains per day, the number of hours and minutes on the planet, and the boarding time for each passenger tram.

$n$ lines follow, each contains two integers $h_i$ and $m_i$ ($0 \le h_i \lt h$, $0 \le m_i \lt m$) — the time when $i$-th freight train departs. It is guaranteed that no freight trains depart at the same time.

输入的第一行包含四个整数 $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 \lt h$，$0 \le m_i \lt m$）——表示第 $i$ 列货运列车的发车时间。保证不存在两列货运列车在同一时刻发车。

The first line of output should contain two integers: the minimum number of trains that need to be canceled, and the optimal starting time $t$. Second line of output should contain freight trains that need to be canceled.

输出的第一行应包含两个整数：需要取消的列车的最少数量，以及最优起始时间 $t$。
输出的第二行应包含需要取消的货运列车。

In the first test case of the example the first tram can depart at 0 hours and 0 minutes. Then the freight train at 16 hours and 0 minutes can depart at the same time as the passenger tram, and the freight train at 17 hours and 15 minutes can depart at the same time as the boarding starts for the upcoming passenger tram.

In the second test case of the example it is not possible to design the passenger tram schedule without cancelling any of the freight trains: if $t \in [1, 15]$, then the freight train at 16 hours and 0 minutes is not able to depart (since boarding time is 16 minutes). If $t = 0$ or $t \in [16, 29]$, then the freight train departing at 17 hours 15 minutes is not able to depart. However, if the second freight train is canceled, one can choose $t = 0$. Another possible option is to cancel the first train and choose $t = 13$.

在示例的第一个测试用例中，首班有轨电车可在 0 时 0 分发车。随后，16 时 0 分的货运列车可与下一班乘客有轨电车同时发车；而 17 时 15 分的货运列车则可与即将开始乘降作业的乘客有轨电车同时发车。

在示例的第二个测试用例中，无法在不取消任何货运列车的前提下设计出满足要求的乘客有轨电车时刻表：若 $t \in [1, 15]$，则 16 时 0 分的货运列车无法发车（因乘降时间为 16 分钟）；若 $t = 0$ 或 $t \in [16, 29]$，则 17 时 15 分发车的货运列车无法发车。然而，若取消第二列货运列车，则可选取 $t = 0$；另一可行方案是取消第一列货运列车，并选取 $t = 13$。