C. Аэротакси
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дракон налил Принцессе ещё чашечку чая. Принцесса чуть заметно вздохнула и спросила:

— А принцессы и принцы в соседних замках — у них тоже договор аренды помещения?

— Конечно! — ответил Дракон, — Но с принцессами, по правде говоря, хлопотно. Так что все прогрессивные драконы стараются сдавать замки в аренду принцам. Впрочем, спрос на замки нынче невелик, приходится аэроизвозом подрабатывать.

Как рассказал Дракон, обитатели замков достаточно часто летают на драконах по разным делам. При этом они крайне не любят «пересекаться» друг с другом и требуют, чтобы по дороге их не видел никто из соседей. Так что диспетчеру, составляющему расписание полётов, приходится непросто.

Мы опишем упрощённую модель происходящего. Будем считать, что воздушное пространство поделено на n «воздушных коридоров». Эти коридоры занумерованы, и каждый из них располагается на определённой высоте: чем меньше номер коридора, тем он выше.

Дракон может начать полёт, заняв любой свободный коридор. Однако в ходе полёта дракон может только снижаться, притом только постепенно. Диспетчер требует, чтобы драконы осуществляли снижение только в целые моменты времени и только на один коридор вниз. Так, если дракон летит по воздушному коридору #j, он может переместиться в воздушный коридор #(j + 1) (если таковой существует). Если дракон занимает какой-либо воздушный коридор, он должен лететь в нём в течение хотя бы одной единицы времени.

В течение всего полёта дракон перемещается с постоянной горизонтальной скоростью, равной единице. Время перемещения между воздушными коридорами пренебрежимо мало и может быть положено равным нулю. Останавливаться в полёте дракон не может. У диспетчера имеется расписание, в котором для каждого воздушного коридора указано время, в течение которого этот коридор занят. Это время представлено множеством интервалов вида (s, f) (s < f); при этом считается, что в моменты времени s и f дракону будет разрешено занимать воздушный коридор, но ни в какие другие моменты времени между s и f он не может этого делать.

Диспетчер получил заявку на полёт длительностью t единиц времени от очередного дракона, и теперь ему нужно выделить для этого полёта воздушные коридоры. Также дракон сообщил, что его пассажир хотел бы прибыть в место назначения как можно раньше.

Ваша задача — определить, в какое время должен стартовать дракон, а также сообщить ему, в какие моменты времени он должен менять воздушный коридор (если, конечно, в этом будет необходимость).

Входные данные

В первой строке содержатся целые числа n и t (1 ≤ n ≤ 100,  1 ≤ t ≤ 10000) — количество воздушных коридоров и длительность полёта дракона.

Каждая из следующих n строк содержит описание занятости воздушного коридора. Это описание состоит из целого числа cj (0 ≤ cj ≤ 100) — количества промежутков времени, в которые занят воздушный коридор #j и собственно перечисления этих промежутков времени. Каждый промежуток состоит из двух целых чисел s(j)k и f(j)k (k = 1, 2, ..., cj), записанных через пробел. При этом 0 ≤ s(j)1 < f(j)1 < s(j)2 < ... < f(j)cj ≤ 109).

Дракон, сделавший заявку на полёт, готов стартовать в любой момент времени, начиная с 0.

Выходные данные

В первой строке выведите целое число a — наиболее ранний момент времени, в который дракон может вылететь.

Во второй строке выведите целые числа h и d — воздушный коридор, с которого дракон начнёт свой полёт и количество перемещений между воздушными коридорами в ходе полёта.

В третьей строке выведите d целых чисел через пробел — моменты времени, в которые дракон должен выполнять переход в другой воздушный коридор.

Если существует несколько вариантов решения, выведите любое из них.

Примеры
Входные данные
2 8
2 0 4 10 20
2 5 10 12 15
Выходные данные
4
1 1
10
Входные данные
5 8
2 0 2 5 10
2 0 4 7 10
1 4 6
2 0 3 5 10
2 0 5 8 10
Выходные данные
0
3 2
3 5
Входные данные
4 9
1 5 9
2 0 4 5 8
2 0 4 5 8
2 0 4 9 12
Выходные данные
8
2 0
Примечание

Поясним приведённые примеры.

В первом примере можно начать полёт в момент времени 4 в первом коридоре, а затем в момент времени 10 спуститься во второй коридор. Полёт завершится в момента времени 12.

Во втором примере полёт можно начать в момент времени 0 в третьем коридоре. В момент времени 3 можно переместиться в четвёртый коридор, в момент времени 5 — в пятый коридор.

В третьем примере самый ранний момент времени, в который можно начать полёт — 8. Действительно, из первого коридора можно было бы переместиться во второй в момент времени 4 и находиться там до момента времени 5. Но перейти в третий коридор уже не получиться: находиться в третьем коридоре после момента времени 5 нельзя. Таким образом, в момент времени 8 можно начать полёт во втором или третьем коридоре и не менять коридор до конца полёта.