402951: GYM100957 F График совещаний

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 строках записано по четыре целых числа a_i, b_i, c_i, d_i, где a_i – время начала первого совещания в i-й день, b_i – время окончания первого совещания в i-день, c_i – время начала второго совещания в i-й день, d_i – время окончания второго совещания в i-й день, 8 ≤ a_i, b_i, c_i, d_i ≤ 18, a_i ≤ b_i, c_i ≤ d_i, a_i ≤ c_i, 1 ≤ i ≤ N.

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

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

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

ПримерВходные данные

1
1
1
11 13 16 17

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

11 12 16 17