F. График совещаний
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

График главного программиста Пети очень напряженный. Каждый день у Пети назначено по два совещания. График совещаний расписан на N дней вперед. У каждого совещания есть время начала и время окончания. Совещания, которые проходят в один день, могут накладываться друг на друга произвольным образом. На работе у Пети действуют следующие правила:

  1. Если первое совещание закончилось позже, чем было назначено начало второго совещания, то из-за задержки время начала и время конца второго совещания сдвигаются на величину задержки. Причем, вне зависимости от величины сдвига, второе совещание будет закончено не позднее окончания рабочего дня (рабочий день заканчивается в 18 часов).
  2. Если в момент окончания первого совещания второе совещание уже должно было закончиться, то второе совещание не переносится, а совсем отменяется.

Так как Петя очень рассеянный, то при внесении расписания совещаний в компьютер он допустил K опечаток. Каждая из опечаток состоит в том, что он записал время начала совещания или время окончания совещания с ошибкой в T часов. Возможна ситуация, что время начала и время окончания одного и того же совещания записаны с ошибкой, это считается за две опечатки. При этом получилось новое расписание, которое обладает следующими свойствами:

  1. Из всех возможных расписаний, которые могли получиться при таком наборе опечаток, получилось такое расписание, при котором общее время пребывания Пети на всех совещаниях минимально.
  2. Время начала и время окончания каждого совещания лежит в пределах от 8 до 18 часов.
  3. Время окончания совещания больше или равно времени начала совещания.
  4. Время начала второго совещания больше или равно времени начала первого совещания.
Входные данные

В первой строке дано целое число N – количество дней, для которых был составлен график совещаний, 1 ≤ N ≤ 1000.

Во второй строке дано целое число K – количество опечаток, которые допустил Петя, 1 ≤ K ≤ 4·N.

В третьей строке дано целое число T – количество часов, на которое ошибался Петя, 1 ≤ T ≤ 10.

В следующих N строках записано по четыре целых числа ai, bi, ci, di, где ai – время начала первого совещания в i-й день, bi – время окончания первого совещания в i-день, ci – время начала второго совещания в i-й день, di – время окончания второго совещания в i-й день, 8 ≤ ai, bi, ci, di ≤ 18, ai ≤ bi, ci ≤ di, ai ≤ ci, 1 ≤ i ≤ N.

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

Программа должна вывести расписание, которое получилось у Пети в следующем формате: в i-й строке должны быть записаны через пробел четыре числа – время начала первого совещания в i-й день, время окончания первого совещания в i-й день, время начала второго совещания в i-й день, время окончания второго совещания в i-й день.

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

Пример
Входные данные
1
1
1
11 13 16 17
Выходные данные
11 12 16 17