Задача №113809. Простыни
В один прекрасный день маленький Дональд решил вымыть N своих чистых белых простыней. После мытья он положил их на землю во дворе, чтобы их высушить. Дональд помещал простыни так, чтобы никакие две простыни не касались ни сторонами, ни углами, и чтобы их стороны не пересекалась, но возможно, что он разместил меньшие простыни поверх более крупных или что простыня полностью закрывает какие-то другие простыни. Сделав это, Дональд лег спать.
Друг Дональда Ким как-то узнал о том, что Дональд сушит простыни и решил пообщаться с ним. Он нашел пейнтбольный пистолет своего отца на чердаке. Наряду с пистолетом у него было несколько пейнтбольных мячей, каждый из них имел свой цвет (не обязательно уникальный). Как только Дональд заснул, Ким вошёл во двор к Дональду и начал стрелять пр простыням из пейнтбольного пистолета. Простыни Дональда очень тонкие, поэтому, когда Ким попадает в какую-то простыню, она пропускает краску дальше, на простыню ниже (и та тоже, и так происходит, пока не закончатся простыни и краска не попадет на землю). После того, как Ким использовал все шары, он с радостью покинул двор Дональда. Дональд был очень расстроен, увидев, что случилось с его простынями. Дональд очень заинтересован в правильных данных о преступлении Кима, но он в шоке и не способен думать, поэтому просит вас сказать ему количество цветов на каждой простыне.
Мы можем представлять двор Дональда как бесконечную систему координат, а простыни - как прямоугольники, параллельные осям координат. Выстрелы Кима могут быть представлены как точки в этой системе.
Когда-то в детстве дедушка рассказал Киму, что снаряд никогда не попадает в одну воронку дважды, так что координаты всех выстрелов попарно различны.
Первая строка ввода содержит два числа - количество простынь N ( 1 ≤ N ≤ 80000 ), и количество шаров M ( 1 ≤ M ≤ 80 000 ).
i -я из следующих N строк содержит четыре числа: координаты нижнего левого угла A i , B i ( 1 ≤ A i , B i ≤ 10 9 ) и верхнего правого угла C i , D i , ( 1 ≤ C i , D i ≤ 10 9 ) i -й простыни.
j -я из следующих M строк содержит три числа, где X j , Y j ( 1 ≤ X j , Y j ≤ 10 9 ) - координаты j -го выстрела Кима и K j ( 1 ≤ K j ≤ 10 9 ) - цвет j -го пейнтбольного шара.
i -я из N выходных строк должна содержать количество цветов на i -м листе.
Тесты к данной задаче состоят из трёх групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп.
2 2 1 1 3 3 5 6 10 10 3 3 1 5 1 2
1 0
3 3 1 1 7 7 2 2 6 6 3 3 5 5 4 4 1 2 6 2 4 7 3
3 2 1
1 3 1 1 7 7 2 6 2 4 7 3 4 4 1
3