Woburn Challenge 2001
How James Bond eluded CBS security in their own headquarters has long been a mystery – to avoid publicizing the secret phone number he used, the details were classified, but have now been cleared for public viewing. Below are excerpts from his report.
"With minimal effort, I was in CBS headquarters, having acquired my information. However, I was on the top floor and needed to escape from the building. I quickly made a collect call to London (just by dialing --, then , then the number, for only 10¢ a minute) where I asked P to fix the elevators for me. You see, I knew that before CBS security could mobilize, they needed to hold a board meeting and some focus groups to decide on an appropriate course of action. To hold a meeting, all the people would need to be on the same floor at the same time. Thus, if I could slow down their ability to meet in one place, I would have enough time to escape. Showing an unusual burst of competence, P quickly hacked into the elevator control system (which just happens to be accessible by Internet), and changed the elevator controls so that each elevator now followed a fixed route regardless of what buttons are pushed (i.e. it might visit floors -------...).
Having already patched into CBS communication channels, I knew that security had been notified that a meeting was urgently necessary. The chief of security had determined that the elevators were "wonky" and was trying to determine what floor to meet on so that the meeting could be held at the earliest possible time. I knew where everyone in the building was located and P had told me the "schedules" that the elevators follow, so I was able to figure out the shortest amount of time before a meeting could have been held, and on which floor this meeting could take place. It's a good thing the building had no stairs. Now I knew how much time I had to escape and which floor to avoid."
Input Specification
The first line contains , the number of test cases.
The first line of each test case contains the positive integers , the
number of floors in the building, , the number of elevators, and
, the number of people . The next line contains
integers giving the locations of all the people in the building.
Each of the next lines contains the "schedule" for an elevator: a
positive integer representing the number of
floors which that elevator visits, followed by integers between
and giving that elevator's schedule. No two consecutive integers in
the schedule will be identical (including the first and last).
Assume the following:
- All elevators move at the speed of floor/minute
- Every elevator starts with its doors open on the first floor listed in its schedule at
- A person can get in/out of an elevator instantaneously
Output Specification
For each test case, output a line containing , the least number of
minutes before a meeting can be held, and the floor on which the
meeting could take place at this time. If it could take place on several
floors, choose the lowest (nosebleeds can be deadly). If no meeting is
possible, output Impossible
.
Sample Input
2
5 3 3
1 3 5
2 1 2
3 5 2 3
2 3 4
4 2 3
1 3 4
2 1 2
2 3 4
Sample Output
4 3
Impossible
Comments