Time Planner

Problems in computer science are often grouped into classes (NP, NP-complete, unsolvable, and so on). Whatever class of problems a team has to solve, there is always one recurring problem: finding a time when all the programmers can meet to work together on their project.

Given every member's busy calendar, your task is to write a program that finds every possible meeting window for the team.

The first line contains the number of scenarios.

Each scenario begins with a line containing the number of team members $m$ ($2 \le m \le 20$). For each team member, there is a line with the number of calendar entries $n$ ($0 \le n \le 100$), followed by $n$ lines in this format:

YYYY MM DD hh mm ss YYYY MM DD hh mm ss some string here

Each line gives the year, month, day, hour, minute, and second of both the start and the end of an appointment, followed by a description string. All numbers are zero-padded to the width shown and separated by single spaces. The description may contain spaces and is at most 100 characters long. All dates lie between January 1, 1800 (midnight) and January 1, 2200 (midnight). For simplicity, assume every month has exactly 30 days, and no invalid date (such as January 31) ever occurs.

Note that the end time of an appointment is the moment the member becomes free again and is ready to join a meeting.

For each scenario, first print a line Scenario #i:, where $i$ is the scenario number starting from 1. Then print one line for every possible meeting window, where a valid meeting satisfies all of the following:

• at every moment of the meeting, at least two team members are present;
• at every moment of the meeting, at most one team member is absent;
• the meeting lasts at least one hour;
• all team members are willing to work 24 hours a day.

For example, with three members A, B, and C, this is a valid meeting: it begins with only A and B; later C joins, and before it ends A may leave.

Always print the longest possible window that satisfies these conditions, even if it is as long as 400 years. Sort the lines by date and time, using this format:

appointment possible from MM/DD/YYYY hh:mm:ss to MM/DD/YYYY hh:mm:ss

The month, day, year, hour, minute, and second must be zero-padded to the required width. If no meeting is possible, print a single line containing no appointment possible. Separate the output of consecutive scenarios with a blank line.