Description

Background

Problems in computer science are often classified as belonging to a certain class of problems (e.g. NP, NP complete, unsolvable, . . . ). Whatever class of problems you have to solve in a team, there is always one main problem: To find a date where all the programmers can meet to work together on their project.

Problem

Your task is to write a program that finds all possible appointments for a programming team that is busy all the time and therefore has problems in finding accurate dates and times for their meetings.

Input

The first line of the input contains the number of scenarios.

For each scenario, you are first given the number m of team members in a single line, with 2 <= m <= 20.For every team member, there will be a line containing the number n of entries in this members calender (0 <= n <= 100), followed by n lines in the following format:

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

Each such line contains the year, month, day, hour, minute, and second of both starting and ending time for the appointment, and a string with the description of the appointment. All numbers are zero padded to match the given format, with single blanks in-between. The string at the end might contain blanks and is no longer than 100 characters. The dates are in the range January 1, 1800 midnight to January 1, 2200 midnight. For simplification, you may assume that all months (even February) have 30 days each, and no invalid dates (like January 31) will occur.

Note that the ending time of a team member's appointment specifies the point in time where this team member is ready to join a meeting.

Output

The output for each scenario begins with a line containing Scenario #i:, where i is the number of the scenario starting at 1. Then print a line for each possible appointments that follows these rules:

• at any time during the meeting, at least two team members need to be there

<li>at any time during the meeting, at most one team member is allowed to be absent</li>

<li>the meeting should be at least one hour in length</li>

<li>all team members are willing to work 24 hours a day</li>

For example, if there are three team members A, B and C, the following is a valid meeting: It begins solely with A and B. Later C joins the meeting and before the end, A may leave.

Always print the longest appointment possible satisfying these conditions, even if it is as long as 400 years. Sort these lines by date and time, and use the following format:

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

The numbers indicating month, day, year, hour, minute, and second should be zero padded in order to get the required number of characters. If no appointment is possible, just print a line containing no appointment possible Conclude the output for each scenario with a blank line.

2
3
3
2002 06 28 15 00 00 2002 06 28 18 00 00 TUD Contest Practice Session
2002 06 29 10 00 00 2002 06 29 15 00 00 TUD Contest
2002 11 15 15 00 00 2002 11 17 23 00 00 NWERC Delft
4
2002 06 25 13 30 00 2002 06 25 15 30 00 FIFA World Cup Semifinal I
2002 06 26 13 30 00 2002 06 26 15 30 00 FIFA World Cup Semifinal II
2002 06 29 13 00 00 2002 06 29 15 00 00 FIFA World Cup Third Place
2002 06 30 13 00 00 2002 06 30 15 00 00 FIFA World Cup Final
1
2002 06 01 00 00 00 2002 06 29 18 00 00 Preparation of Problem Set
2
1
1800 01 01 00 00 00 2200 01 01 00 00 00 Solving Problem 8
0

Scenario #1:
appointment possible from 01/01/1800 00:00:00 to 06/25/2002 13:30:00
appointment possible from 06/25/2002 15:30:00 to 06/26/2002 13:30:00
appointment possible from 06/26/2002 15:30:00 to 06/28/2002 15:00:00
appointment possible from 06/28/2002 18:00:00 to 06/29/2002 10:00:00
appointment possible from 06/29/2002 15:00:00 to 01/01/2200 00:00:00

Scenario #2:
no appointment possible

Source

TUD Programming Contest 2002, Darmstadt, Germany