eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Маляри

Маляри

Ліміт часу 3 секунди
Ліміт використання пам'яті 256 MiB

Малярна фірма отримала замовлення на фарбування огорожі. Огорожа була дуже довгою, тому фарбуваии її довелось декільком малярам. Менеджер фірми видавав завдання кожному наступному маляру фарбувати огорожу від дошки з номером X до дошки з номером Y (включно) у колір Z після того, як попередній маляр завершив роботу. На жаль, менеджер трохи наплутав при видачв завдань і деякі дошки, можливо, пофарбовано декілька разів, а деякі не пофарбовані взагалі. Директор фірми зібрав записи усіх малярів і повинен вирішити, у який колір простіше перефарбувати всю огорожу заново.

Визначте, будь-ласка, скільки дошок якого кольору у пофарбованій огорожі.

Вхідні дані

У першому рядку одне натуральне число N – кількість працювавших малярвв, N10^5. Потім N рядків по три цілих числа, X_i, Y_i, Z_i через пропуск, 0X_i, Y_i10^9, 1Z_i10^5 – номер першої пофарбованої дошки, номер останньої пофарбованої дошки, колір.

Вихідні дані

Позначимо через M кількість кольорів, у які пофарбовано дошки. Виводяться M рядків, у кожному з яких по 2 натуральних числа через один пропуск: номер кольору та число дощок цього кольору. Вивід упорядкувати за зростанням номера кольору.

Приклад

Вхідні дані #1
3
2 3 1
1 5 10
3 8 5
Вихідні дані #1
5 6
10 2
Джерело ACM ICPC 2012-2013 NEERC Siberian Group