Прямоугольники в квадрате

В двух отраслях — электронике и телекоммуникациях — прогресс материализуется настолько зримо, что начинаешь воспринимать его как природную силу, управляющую судьбами людей и компаний и преображающую человеческую жизнь. Мэйнфреймы, мини-компьютеры, микрокомпьютеры, LAN, WAN, Интернет, оптоволокно, встроенные системы, широкополосная передача данных — целые эпохи вычислений и коммуникаций сменяли друг друга на отрезке времени намного короче человеческой жизни — длиной всего-то в 30 лет. Прогресс имеет свои жизненные циклы, и периоды роста в производстве полупроводниковых блоков примерно раз в пять лет чередуются с периодами спада. Но это спад и рост только по количеству, многие эксперты сходятся во мнении, что количественный спад — лишь передышка, в течение которой прогресс накапливает силы для нового качественного рывка. Сегодня основной причиной спада в мировой полупроводниковой отрасли эксперты называют недостаток инструментальных средств нового поколения для автоматизированного проектирования электронных систем (EDA, Electronic Design Automation), которые позволили бы учитывать возможности, открывающиеся благодаря последним достижениям в технологиях производства полупроводниковых структур (переход к нанометровым технологиям).

На очень общем уровне процесс проектирования электронных систем включает в себя четыре стадии:
1) проработка идеи и постановка технического задания;
2) создание функциональной схемы;
3) разработка принципиальной схемы, размещение компонентов и трассировка проводников на плате;
4) физическое воплощение.

В данной задаче нам требуется помочь разработчикам современных EDA c третьим этапом проектирования. Представим подложку, на которой необходимо разместить полупроводниковые элементы, в виде квадрата. У нас также имеется некоторый набор прямоугольных полупроводниковым элементов, которые необходимо разместить на подложке оптимальным образом. При этом элементы не должны пересекаться между собой и выходить за пределы квадрата. Естественно, что место не должно пропадать даром, поэтому, чем меньше площади останется незаполненной, тем компактнее получится разработанная система. Процесс проектирования окажется более эффективным и позволит избежать ненужных затрат на производство лишних подложек!

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

t – число тестовых последовательностей, затем следуют t тестовых последовательностей. [t <= 500]
На первой строчке каждой тестовой последовательности стоит целое число N, а на второй строчке целое число K. Где N - это длина стороны квадрата [2 <= N <= 1000], а K - число различных доступных прямоугольников [1 <= K <= 10000]. Затем следуют ровно K строк, на каждой из которых стоят 3 числа: wi, hi, li. wi - длина прямоугольника [wi <= N], hi - высота прямоугольника [hi <= N], li - количество таких прямоугольников [li <= 200000]. Вы можете вращать прямоугольники на угол кратный 90 градусов.

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

Для каждого теста выведите число R - количество использованных прямоугольников, за которым следуют ровно R строк. В каждой строке выведите целые координаты противоположных углов каждого из прямоугольников xi1, yi1, xi2, yi2. Решение будет считаться верным (accepted) если все выведенные прямоугольники не будут пересекаться между собой, и не будут выходить за границы квадрата.

Начисление очков

Общие очки равны сумме очков полученных индивидуально за каждый из тестов. Количество очков за каждый тест равно суммарной покрытой площади квадрата деленное на площадь квадрата. За тест, в котором квадрат с длиной стороны N покрыт целиком, вы получите 4 очка. Если полученные вами очки выглядят как xxx.xxxaaa, то число aaa = числу полностью покрытых квадратов.

Пример

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

1
10
8
3 5 2
2 2 1
2 3 1
2 5 1
4 5 1
1 3 2
3 8 1
1 1 1

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

9
1 1 5 3
6 1 8 5
9 1 10 2
1 4 5 7
6 6 10 7
9 3 10 5
1 8 1 10
2 8 2 10
3 8 10 10

Пояснение, к примеру:

На рисунке прямоугольники помечены номерами в соответствии с порядком следования в выходных данных примера.
За данный тест, так как квадрат оказался покрыт целиком, вы получите 4.000001 очков.