Задача B. Космос для школьников

Автор:В. Гринько   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Два друга Игорь и Олег — ученики 8 класса. В будущем они очень хотят запустить на космическую орбиту спутник собственной разработки. Однако они опасаются, что их спутник может столкнуться с другими спутниками, летающими вокруг земли.

Учитель астрономии решил поддержать юных исследователей и выдал друзьям список существующих спутников, которые будут пролетать над городом, где живут Игорь с Олегом, в день предполагаемого запуска их спутника. Для каждого из N спутников в списке указан момент его пролёта над городом с точностью до минуты.

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

Формат входного файла

В первой строке входного файла содержится число N. Далее следуют N строк вида HH:MM, где HH — часы, MM — минуты.

Формат выходного файла

Выходной файл должен содержать последовательность строк вида HH:MM - HH:MM или HH:MM — интервалы времени, в течение которых над городом нет спутников. Интервалы должны быть расположены в хронологическом порядке.

Количество интервалов должно быть минимально возможным. Например, вместо двух интервалов 00:00 - 05:30, 05:31 - 06:00 нужно вывести один интервал 00:00 - 06:00.

Если не существует интервала, когда над городом нет ни одного спутника, выходной файл должен содержать единственную строку NONE.

Ограничения

1 ≤ N ≤ 1440

0 ≤ H ≤ 23

0 ≤ M ≤ 59

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
2
10:10
10:12
00:00 - 10:09
10:11
10:13 - 23:59
2
4
10:11
10:12
10:10
10:13
00:00 - 10:09
10:14 - 23:59

0.184s 0.024s 15