Маляри#4206
Малярна фірма отримала замовлення на фарбування огорожі. Огорожа була дуже довгою, тому фарбувати її довелось декільком малярам. Менеджер фірми видавав завдання кожному наступному маляру фарбувати огорожу від дошки з номером до дошки з номером (включно) у колір після того, як попередній маляр завершив роботу. На жаль, менеджер трохи наплутав при видачі завдань і деякі дошки, можливо, пофарбовано декілька разів, а деякі не пофарбовані взагалі. Директор фірми зібрав записи усіх малярів і повинен вирішити, у який колір простіше перефарбувати всю огорожу заново.
Визначте, будь ласка, скільки дошок якого кольору у пофарбованій огорожі.
У першому рядку одне натуральне число (N \leq 10^5) — кількість працюючих малярів. Потім рядків по три цілих числа, X_i, Y_i, Z_i через пропуск, 0 \leq X_i, Y_i \leq 10^9, 1 \leq Z_i \leq 10^5 — номер першої пофарбованої дошки, номер останньої пофарбованої дошки, колір.
Позначимо через кількість кольорів, у які пофарбовано дошки. Виводяться рядків, у кожному з яких по натуральних числа через один пропуск: номер кольору та число дошок цього кольору. Вивід упорядкувати за зростанням номера кольору.
Приклад 1