21688번 - Информатизация садоводства 스페셜 저지다국어

Дачный участок Степана Петровича имеет форму прямоугольника размером a × b. На участке имеется n построек, причем основание каждой постройки — прямоугольник со сторонами, параллельными сторонам участка.

Вдохновленный успехами соседей, Степан Петрович хочет посадить на своем участке m видов плодовых культур (участок Степана Петровича находится в северной местности, поэтому m = 1 или m = 2). Для каждого вида растений Степан Петрович хочет выделить отдельную прямоугольную грядку со сторонами, параллельными сторонам участка. Само собой, грядки не могут занимать территорию, занятую постройками или другими грядками.

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

Требуется по заданным размерам участка и координатам построек определить оптимальное расположение грядок.

В первой строке входного файла содержатся два целых числа n и m (0 ≤ n ≤ 10; 1 ≤ m ≤ 2).

Во второй строке содержатся два целых числа a и b (1 ≤ a, b ≤ 10000).

Далее следуют n строк, каждая из которых содержит четыре целых числа x_i,1, y_i,1, x_i,2, y_i,2 –координаты двух противоположных углов постройки (0 ≤ x_i,1 < x_i,2 ≤ a, 0 ≤ y_i,1 < y_i,2 ≤ b). Различные постройки не могут пересекаться, но могут касаться друг друга.

В выходной файл выведите m строк, каждая из которых содержит координаты двух противоположных углов предлагаемой грядки. Координаты должны быть целые (всегда можно добиться максимальной суммарной площади грядок, располагая их в прямоугольниках с целыми координатами). 

В случае, если в вашем решении Степану Петровичу следует посадить менее m грядок, выведите для грядок, которые не следует сажать, строку «0 0 0 0» (см. пример 2).