Маляры
Малярная фирма получила заказ на покраску забора. Забор был очень длинный, поэтому красить его пришлось нескольким малярам. Менеджер фирмы выдавал задание каждому следующему маляру красить забор от доски с номером X до доски с номером Y (включительно) в цвет Z после того, как предыдущий маляр закончил работу. К сожалению, менеджер немного напутал при выдаче заданий и некоторые доски, возможно, покрашены несколько раз, а некоторые не покрашены вообще. Директор фирмы собрал записи всех маляров и должен решить, в какой цвет проще перекрасить весь забор заново.
Определите, пожалуйста, сколько досок какого цвета в покрашенном заборе.
Входные данные
В первой строке одно натуральное число N – число работавших маляров, N ≤ 10^5. Затем N строк по три целых числа, X_i, Y_i, Z_i через пробел, 0 ≤ X_i, Y_i ≤ 10^9, 1 ≤ Z_i ≤ 10^5 – номер первой покрашенной доски, номер последней покрашенной доски, цвет.
Выходные данные
Обозначим через M число цветов, в которые окрашены доски. Выводятся M строк, в каждой из которых по 2 натуральных числа через один пробел: номер цвета и число досок этого цвета. Вывод упорядочить по возрастанию номера цвета.