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 < {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 < k$, then the freight trains can not depart during the last $k - t$ minutes of the day.

 $O$ 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.


-----Input-----

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 < h$, $0 \le m_i < m$) — the time when $i$-th freight train departs. It is guaranteed that no freight trains depart at the same time.


-----Output-----

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.


-----Examples-----
Input
2 24 60 15
16 0
17 15

Output
0 0


Input
2 24 60 16
16 0
17 15

Output
1 0
2 



-----Note-----

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$.

Source: codeforces | Difficulty: HARD
Tags: Data structures

Sorting

Amortized analysis

Complete search


Solutions:
import sys
sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]
(n, H, M, k) = MI()
hm = LLI(n)
M2 = M // 2
ll = []
rr = []
st = set([0, M2])
for (h, m) in hm:
	s = (m + 1) % M2
	ll.append(s)
	rr.append(s + k - 1)
	st.add(s)
	st.add(s + M2)
	st.add((s + k - 1) % M2)
	st.add((s + k - 1) % M2 + M2)
dec = list(sorted(st))
enc = {a: i for (i, a) in enumerate(dec)}
ln = len(dec)
tt = [0] * ln
for (l, r) in zip(ll, rr):
	tt[enc[l]] += 1
	tt[enc[r]] -= 1
for i in range(ln - 1):
	tt[i + 1] += tt[i]
for i in range(ln // 2):
	tt[i] += tt[i + ln // 2]
mn = min(tt[:ln // 2])
i = tt[:ln // 2].index(mn)
t = dec[i]
ans = []
for (i, (l, r)) in enumerate(zip(ll, rr)):
	if l <= t < r or l <= t + M2 < r:
		ans.append(i + 1)
print(mn, t)
print(*ans)


from collections import defaultdict
import sys
input = sys.stdin.readline
(n, h, m, k) = map(int, input().split())
l = []
a = []
start = 0
for i in range(n):
	(H, M) = map(int, input().split())
	M = M % (m // 2)
	a.append(M)
	l.append((M + 1, 1, i))
	l.append(((M + k) % (m // 2), -1, i))
	if M + 1 > (M + k) % (m // 2):
		start += 1
l.sort()
p = -1
ans = (10000000000, 0)
for (t, dire, ind) in l:
	if p != -1 and p != t:
		ans = min(ans, (start, p))
	start += dire
	p = t
print(*ans)
time = ans[1]
if ans[0] > 0:
	for i in range(n):
		if a[i] + 1 > (a[i] + k - 1) % (m // 2):
			if time >= a[i] + 1 or time <= (a[i] + k - 1) % (m // 2):
				print(i + 1)
		elif time >= a[i] + 1 and time <= (a[i] + k - 1) % (m // 2):
			print(i + 1)


import sys
from collections import deque
input = sys.stdin.buffer.readline
(n, h, m, k) = map(int, input().split())
tram = []
dic = {}
for i in range(n):
	(H, M) = map(int, input().split())
	r = M % (m // 2)
	tram.append(r)
	if r not in dic:
		dic[r] = 0
	dic[r] += 1
data = [(i, dic[i]) for i in dic] + [(i + m // 2, dic[i]) for i in dic]
data.sort()
k -= 1
add = deque([])
erase = deque([])
for (i, val) in data:
	add.append((i - k + 1, val))
	erase.append((i + 1, -val))
S = 0
while add and add[0][0] <= 0:
	(t, val) = add.popleft()
	S += val
while erase and erase[0][0] <= 0:
	(t, val) = erase.popleft()
	S += val
ans = S
res = 0
while add or erase:
	time = 10 ** 15
	if add:
		time = min(time, add[0][0])
	if erase:
		time = min(time, erase[0][0])
	if time >= m // 2:
		break
	while add and add[0][0] == time:
		(time, val) = add.popleft()
		S += val
	while erase and erase[0][0] == time:
		(time, val) = erase.popleft()
		S += val
	if ans > S:
		ans = S
		res = time
Ans = ans
print(Ans, (res + k) % (m // 2))
ans = []
for i in range(n):
	L = res
	R = res + k - 1
	if R >= tram[i] >= L or R >= tram[i] + m // 2 >= L:
		ans.append(i + 1)
print(*ans)


import io
import os
from collections import Counter, defaultdict, deque

def solve(N, H, M, K, HM):
	assert M % 2 == 0
	HALFHOUR = M // 2
	freightTimes = [(h * M + m) % HALFHOUR for (h, m) in HM]
	freightTimes.sort()
	freightTimes = freightTimes + [x + HALFHOUR for x in freightTimes]
	window = deque()
	freq = Counter()
	best = (float('inf'),)
	for x in freightTimes:
		window.append(x)
		freq[x] += 1
		while x - window[0] > K:
			freq[window.popleft()] -= 1
		if x >= K:
			if window:
				cost = len(window)
				if window[-1] - window[0] == K:
					cost -= freq[window[-1]]
					cost -= freq[window[0]]
				else:
					cost -= freq[window[-1]]
				best = min(best, (cost, x % HALFHOUR))
	(covered, t) = best
	cancel = []
	for (i, (h, m)) in enumerate(HM):
		m = m % HALFHOUR
		if t - K < 0:
			if 0 <= m < t or (t - K) % HALFHOUR < m < HALFHOUR:
				cancel.append(str(i + 1))
		elif t - K < m < t:
			cancel.append(str(i + 1))
	assert len(cancel) == covered
	return str(len(cancel)) + ' ' + str(t) + '\n' + ' '.join(cancel)
if False:
	import random
	random.seed(0)
	for _ in range(10000):
		N = random.randint(1, 100)
		H = random.randint(1, 24)
		M = random.randint(1, 30) * 2
		K = random.randint(1, M // 2)
		HM = [(random.randint(0, H - 1), random.randint(0, M - 1)) for i in range(N)]
		solve(N, H, M, K, HM)
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(N, H, M, K) = [int(x) for x in input().split()]
HM = [[int(x) for x in input().split()] for i in range(N)]
ans = solve(N, H, M, K, HM)
print(ans)


from sys import stdin
(n, h, m, k) = map(int, stdin.readline().split())
now = 0
ends = []
starts = []
ppp = [0] * n
for i in range(n):
	(hi, mi) = map(int, stdin.readline().split())
	if mi >= m // 2:
		pz = mi - m
	else:
		pz = mi
	if 0 <= pz < m // 2:
		starts.append((pz, i))
	if -k < pz <= m // 2 - k:
		ends.append((pz, i))
		if -k < pz < 0:
			now += 1
			ppp[i] = 1
	if m // 2 <= mi < m:
		starts.append((mi - m // 2, i))
	if m // 2 - k < mi <= m - k:
		ends.append((mi - m // 2, i))
		if m // 2 - k < mi < m // 2:
			now += 1
			ppp[i] = 1
ends.sort()
starts.sort()
ends.append((float('inf'), 0))
starts.append((float('inf'), 0))
ei = 0
si = 0
sub = now
ans = now
while ei != len(ends) - 1 or si != len(starts) - 1:
	if ends[ei][0] <= starts[si][0] - k:
		now -= 1
		ei += 1
	else:
		si += 1
		now += 1
	ans = min(ans, now)
import sys
ei = 0
si = 0
now = sub
nt = 0
if ans == now:
	print(ans, nt)
	ll = []
	for i in range(n):
		if ppp[i] == 1:
			ll.append(i + 1)
	print(*ll)
	sys.exit()
while ei != len(ends) - 1 or si != len(starts) - 1:
	nt = 0
	if ends[ei][0] <= starts[si][0] - k:
		nt = ends[ei][0] + k
		now -= 1
		ppp[ends[ei][1]] = 0
		ei += 1
	else:
		nt = starts[si][0]
		ppp[starts[si][1]] = 1
		si += 1
		now += 1
	if ans == now:
		print(ans, nt)
		ll = []
		for i in range(n):
			if ppp[i] == 1:
				ll.append(i + 1)
		print(*ll)
		sys.exit()


import sys
import re

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return map(int, minp().split())

def solve():
	(n, h, m, k) = mints()
	m //= 2
	a = [0] * n
	e = [None] * (2 * n + 2)
	c = 0
	for i in range(n):
		(hh, mm) = mints()
		x = mm % m
		a[i] = mm
		e[2 * i] = ((x + k) % m, -1, i)
		e[2 * i + 1] = ((x + 1) % m, 1, i)
		if (x + 1) % m > (x + k) % m:
			c += 1
	e[2 * n] = (0, 0, 0)
	e[2 * n + 1] = (m - 1, 0, 0)
	e.sort()
	p = -1
	r = (int(1000000000.0), 0)
	for (x, t, id) in e:
		if p != x and p != -1:
			r = min(r, (c, p))
		p = x
		c += t
	r = min(r, (c, p))
	print(*r)
	p = r[1]
	for i in range(n):
		mm = a[i]
		x = (mm - p) % m
		if (x + 1) % m > (x + k) % m and (x + k) % m != 0 or ((x + 1) % m < (x + k) % m and (x + 1) % m == 0):
			print(i + 1, end=' ')
solve()


import os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, h, m, k) = map(int, input().split())
trainMod = []
for i in range(n):
	(hi, mi) = map(int, input().split())
	trainMod.append((mi % (m // 2), i + 1))
	if mi % (m // 2) <= k:
		trainMod.append((mi % (m // 2) + m // 2, i + 1))
trainMod.sort(key=lambda x: x[0])
leftIndex = 0
minCancelledTrain = n
startTime = 0
cancelLeft = 0
cancelRight = n
for i in range(len(trainMod)):
	if trainMod[i][0] < k:
		continue
	while trainMod[leftIndex][0] <= trainMod[i][0] - k:
		leftIndex += 1
	if minCancelledTrain > i - leftIndex:
		minCancelledTrain = i - leftIndex
		startTime = trainMod[i][0] % (m // 2)
		cancelLeft = leftIndex
		cancelRight = i
print(str(minCancelledTrain) + ' ' + str(startTime))
cancelTrain = []
for i in range(cancelLeft, cancelRight):
	cancelTrain.append(str(trainMod[i][1]))
print(' '.join(cancelTrain))


import sys
import collections
inpy = [int(x) for x in sys.stdin.read().split()]
(n, h, m, k) = inpy[:4]
rm = [0] * n
index = 4
for i in range(n):
	rm[i] = (inpy[index + 1], i + 1)
	index += 2
(res, cancle) = (0, None)
rm.sort()
rm = rm + [(i[0] + m, i[1]) for i in rm]
(s1, s2, e2) = (0, 0, 0)
q1 = collections.deque()
q2 = collections.deque()
res = 99
x = 99999999
for i in range(n):
	while s1 < 2 * n:
		if rm[s1][0] < rm[i][0] + k:
			q1.append(rm[s1])
			s1 += 1
		else:
			break
	while s2 < 2 * n:
		if rm[s2][0] < rm[i][0] + m // 2 + k:
			q2.append(rm[s2])
			s2 += 1
		else:
			break
	while q1 and q1[0][0] <= rm[i][0]:
		q1.popleft()
	while q2 and q2[0][0] <= rm[i][0] + m // 2:
		q2.popleft()
	if x > len(q1) + len(q2):
		res = rm[i][0] + k
		x = len(q1) + len(q2)
a = res
while a >= m // 2:
	a -= m // 2
print(x, a)
for i in rm:
	if res - k < i[0] < res or res - k + m // 2 < i[0] < res + m // 2:
		print(i[1])


import sys
from bisect import bisect_left, bisect_right
input = sys.stdin.buffer.readline
(n, h, m, k) = map(int, input().split())
(p, trm) = (m // 2, [])
for i in range(n):
	(a, b) = map(int, input().split())
	trm.append((b % p, i + 1))
trm.sort()
tls = [t for (t, _) in trm]
(mxn, mxt, mxrng) = (0, 0, [])
for (t, _) in trm:
	rng = []
	if t + k <= p:
		rng.append((0, t))
		rng.append((t + k, p))
	else:
		rng.append((t + k - p, t))
	cc = 0
	for (a, b) in rng:
		pa = bisect_left(tls, a)
		pb = bisect_right(tls, b)
		cc += pb - pa
	if cc > mxn:
		(mxt, mxn, mxrng) = (t + k, cc, rng)
used = [0] * (n + 1)
for (a, b) in mxrng:
	pa = bisect_left(tls, a)
	pb = bisect_right(tls, b)
	for u in range(pa, pb):
		used[trm[u][1]] = 1
cancel = [u for u in range(1, n + 1) if not used[u]]
print(n - mxn, mxt % p)
print(*cancel)


(n, H, M, k) = map(int, input().split())
hm = []
for i in range(n):
	hm.append(list(map(int, input().split())))
M2 = M // 2
ll = []
rr = []
st = {0, M2}
for (h, m) in hm:
	s = (m + 1) % M2
	ll.append(s)
	rr.append(s + k - 1)
	st.add(s)
	st.add(s + M2)
	st.add((s + k - 1) % M2)
	st.add((s + k - 1) % M2 + M2)
dec = list(sorted(st))
enc = {a: i for (i, a) in enumerate(dec)}
ln = len(dec)
tt = [0] * ln
for (l, r) in zip(ll, rr):
	tt[enc[l]] += 1
	tt[enc[r]] -= 1
for i in range(ln - 1):
	tt[i + 1] += tt[i]
for i in range(ln // 2):
	tt[i] += tt[i + ln // 2]
mn = min(tt[:ln // 2])
i = tt[:ln // 2].index(mn)
t = dec[i]
ans = []
for (i, (l, r)) in enumerate(zip(ll, rr)):
	if l <= t < r or l <= t + M2 < r:
		ans.append(i + 1)
print(mn, t)
print(*ans)


import sys
input = sys.stdin.readline
(n, h, m, k) = map(int, input().split())
tram = []
dic = {}
for i in range(n):
	(H, M) = map(int, input().split())
	r = M % (m // 2)
	tram.append(r)
	if r not in dic:
		dic[r] = 0
	dic[r] += 1
S = [i for i in dic]
for i in S:
	dic[i + m // 2] = 0
	dic[i + m // 2] = dic[i]
data = [(i, dic[i]) for i in dic]
data.sort()
if k == 1:
	print(0, 0)
	print(*[])
	exit()
k -= 1
query = []
for i in dic:
	query.append((i + 1, -dic[i]))
	query.append((i - k + 1, dic[i]))
query.sort(reverse=True)
S = 0
while query and query[-1][0] <= 0:
	(t, val) = query.pop()
	S += val
ans = S
res = 0
while query and query[-1][0] < m // 2:
	(time, val) = query.pop()
	S += val
	while query and query[-1][0] == time:
		(time, val) = query.pop()
		S += val
	if ans > S:
		ans = S
		res = time
Ans = ans
print(Ans, (res + k) % (m // 2))
ans = []
for i in range(n):
	L = res
	R = res + k - 1
	if R >= tram[i] >= L or R >= tram[i] + m // 2 >= L:
		ans.append(i + 1)
if len(ans) != Ans:
	print('WA')
print(*ans)


import sys
from array import array
from typing import Dict, List, Tuple, TypeVar, Generic, Sequence, Union

def input():
	return sys.stdin.buffer.readline().decode('utf-8')

def main():
	from collections import defaultdict
	from bisect import bisect_left, bisect_right
	(n, h, m, k) = map(int, input().split())
	half = m >> 1
	a = []
	indexes: Dict[int, List] = defaultdict(list)
	for (i, (_, mi)) in enumerate((map(int, input().split()) for _ in range(n)), start=1):
		a.extend((mi, (mi + half) % m))
		indexes[mi].append(i)
		indexes[(mi + half) % m].append(i)
	a.sort()
	r = bisect_left(a, half)
	l = bisect_left(a, a[r] - k + 1)
	(ans, ans_t) = (r - l, a[r])
	for r in range(r + 1, len(a)):
		time = a[r]
		while a[l] <= time - k:
			l += 1
		if ans > r - l:
			ans = r - l
			ans_t = a[r]
	cancel = []
	for time in set(a):
		if ans_t - k < time < ans_t:
			cancel.extend(indexes[time])
	print(ans, ans_t - half)
	print(*cancel)
main()


from bisect import *
from collections import *
from math import gcd, ceil, sqrt, floor, inf
from heapq import *
from itertools import *
from operator import add, mul, sub, xor, truediv, floordiv
from functools import *
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
farr = [1]
ifa = []

def fact(x, mod=0):
	if mod:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr) % mod)
	else:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr))
	return farr[x]

def ifact(x, mod):
	global ifa
	ifa.append(pow(farr[-1], mod - 2, mod))
	for i in range(x, 0, -1):
		ifa.append(ifa[-1] * i % mod)
	ifa = ifa[::-1]

def per(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return fact(i) // fact(i - j)
	return farr[i] * ifa[i - j] % mod

def com(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return per(i, j) // fact(j)
	return per(i, j, mod) * ifa[j] % mod

def catalan(n):
	return com(2 * n, n) // (n + 1)

def linc(f, t, l, r):
	while l < r:
		mid = (l + r) // 2
		if t > f(mid):
			l = mid + 1
		else:
			r = mid
	return l

def rinc(f, t, l, r):
	while l < r:
		mid = (l + r + 1) // 2
		if t < f(mid):
			r = mid - 1
		else:
			l = mid
	return l

def ldec(f, t, l, r):
	while l < r:
		mid = (l + r) // 2
		if t < f(mid):
			l = mid + 1
		else:
			r = mid
	return l

def rdec(f, t, l, r):
	while l < r:
		mid = (l + r + 1) // 2
		if t > f(mid):
			r = mid - 1
		else:
			l = mid
	return l

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def binfun(x):
	c = 0
	for w in arr:
		c += ceil(w / x)
	return c

def lowbit(n):
	return n & -n

def inverse(a, m):
	a %= m
	if a <= 1:
		return a
	return (1 - inverse(m, a) * m) // a % m

class BIT:

	def __init__(self, arr):
		self.arr = arr
		self.n = len(arr) - 1

	def update(self, x, v):
		while x <= self.n:
			self.arr[x] += v
			x += x & -x

	def query(self, x):
		ans = 0
		while x:
			ans += self.arr[x]
			x &= x - 1
		return ans

class DSU:

	def __init__(self, n):
		self.c = [-1] * n

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def find(self, x):
		if self.c[x] < 0:
			return x
		self.c[x] = self.find(self.c[x])
		return self.c[x]

	def union(self, u, v):
		(u, v) = (self.find(u), self.find(v))
		if u == v:
			return False
		if self.c[u] < self.c[v]:
			(u, v) = (v, u)
		self.c[u] += self.c[v]
		self.c[v] = u
		return True

	def size(self, x):
		return -self.c[self.find(x)]

class UFS:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv

def Prime(n):
	c = 0
	prime = []
	flag = [0] * (n + 1)
	for i in range(2, n + 1):
		if not flag[i]:
			prime.append(i)
			c += 1
		for j in range(c):
			if i * prime[j] > n:
				break
			flag[i * prime[j]] = prime[j]
			if i % prime[j] == 0:
				break
	return prime

def dij(s, graph):
	d = {}
	d[s] = 0
	heap = [(0, s)]
	seen = set()
	while heap:
		(dis, u) = heappop(heap)
		if u in seen:
			continue
		for v in graph[u]:
			if v not in d or d[v] > d[u] + graph[u][v]:
				d[v] = d[u] + graph[u][v]
				heappush(heap, (d[v], v))
	return d

def GP(it):
	return [(ch, len(list(g))) for (ch, g) in groupby(it)]

class DLN:

	def __init__(self, val):
		self.val = val
		self.pre = None
		self.next = None
t = 1
for i in range(t):
	(n, h, m, k) = RL()
	m = m // 2
	s = set()
	res = []
	for i in range(n):
		(hi, mi) = RL()
		s.add(mi % m)
		s.add((mi + k) % m)
		res.append([mi % m, i + 1])
	res.sort()
	ans = inf
	(tl, tr, ty, tt) = (0, 0, 0, 0)
	for pt in s:
		l = bisect(res, [(pt - k) % m, inf])
		r = bisect(res, [pt, -inf])
		if pt - k >= 0:
			tmp = r - l
		else:
			tmp = n - l + r
		if tmp < ans:
			ans = tmp
			tt = pt
			(tl, tr, ty) = (l, r, int(pt - k >= 0))
	print(ans, tt)
	if ty:
		can = [res[i][1] for i in range(tl, tr)]
	else:
		can = [res[i][1] for i in range(tl, n)] + [res[i][1] for i in range(tr)]
	print(*can)


import sys
from bisect import bisect_left, bisect_right
input = sys.stdin.buffer.readline
(n, h, m, k) = map(int, input().split())
(p, trm) = (m // 2, [])
for i in range(n):
	(a, b) = map(int, input().split())
	trm.append((b % p, i + 1))
trm.sort()
tls = [t for (t, _) in trm]

def get_cancel(t):
	r = []
	if t >= k:
		r.append((t - k + 1, t - 1))
	else:
		r.append((0, t - 1))
		r.append((p + (t - k) + 1, p - 1))
	cc = 0
	for (a, b) in r:
		pa = bisect_left(tls, a)
		pb = bisect_right(tls, b)
		cc += max(pb - pa, 0)
	return (cc, r)
(mnn, mnt, mnr) = (n + 1, 0, [])
for t in tls:
	(cc, r) = get_cancel(t)
	if cc < mnn:
		(mnn, mnt, mnr) = (cc, t, r)
res = []
for (a, b) in mnr:
	pa = bisect_left(tls, a)
	pb = bisect_right(tls, b)
	for u in range(pa, pb):
		res.append(trm[u][1])
print(mnn, mnt)
print(*res)