Given a list of scheduled time intervals with in a 24-hour period, the goal is to identify and output the time ranges that are not covered by any of the provided intervals.

Input Format

The first line contains an integer N, rerpesenting the number of schedulde intervals. The following N lines each contain an interval in the format:

HH:MM:SS - HH:MM:SS

All times fall within a single day (00:00:00 to 23:59:59). Intervals are separated by at least 1 second, and they do not overlap (they may only touch at endpoints).

Output Format

Output the missing time intervals in chronological order, using the same HH:MM:SS - HH:MM:SS format. It is guaranteed that at least one missing interval exists.

Example

Input:

8
13:00:00 - 18:00:00
00:00:00 - 01:00:05
08:00:00 - 09:00:00
07:10:59 - 08:00:00
01:00:05 - 04:30:00
06:30:00 - 07:10:58
05:30:00 - 06:30:00
18:00:00 - 19:00:00

Output:

04:30:00 - 05:30:00
07:10:58 - 07:10:59
09:00:00 - 13:00:00
19:00:00 - 23:59:59

Implementation

The following solution converts times into total seconds to map occupied periods. It then scans the entire day to find unmarked segments.

#include <bits/stdc++.h>
using namespace std;

const int TOTAL_SECONDS = 24 * 60 * 60;
bool occupied[TOTAL_SECONDS];

void markInterval(int h_start, int m_start, int s_start, int h_end, int m_end, int s_end) {
    int start = h_start * 3600 + m_start * 60 + s_start;
    int end = h_end * 3600 + m_end * 60 + s_end;
    for (int sec = start; sec < end; ++sec) {
        occupied[sec] = true;
    }
}

void printGap(int& cursor, int& printed) {
    if (cursor >= TOTAL_SECONDS) return;
    if (printed > 0) cout << endl;
    
    int gap_start = cursor;
    printf("%02d:%02d:%02d - ", gap_start / 3600, (gap_start / 60) % 60, gap_start % 60);

    while (cursor < TOTAL_SECONDS && !occupied[cursor]) {
        cursor++;
    }
    
    int gap_end = cursor - 1;
    if (gap_end < 0) gap_end = 0;
    printf("%02d:%02d:%02d", gap_end / 3600, (gap_end / 60) % 60, gap_end % 60);
    printed++;
}

int main() {
    int n;
    cin >> n;
    
    while (n--) {
        int sh, sm, ss, eh, em, es;
        scanf("%d:%d:%d - %d:%d:%d", &sh, &sm, &ss, &eh, &em, &es);
        markInterval(sh, sm, ss, eh, em, es);
    }

    int idx = 0;
    int counter = 0;
    while (idx < TOTAL_SECONDS) {
        if (!occupied[idx]) {
            printGap(idx, counter);
        } else {
            idx++;
        }
    }
    return 0;
}