Clock Gallery
Description
Mr Ritz has just opened his new hotel in Paris. Above the reception desk, he has mounted a vast gallery of $n$ 24-hour clocks to display the current time in many different cities, precise to the second. He proudly cuts the ribbon and welcomes the first guest to check in, only to be informed that the gallery is useless - he has forgotten to label the clocks, so guests have no idea which clock represents each city!
Worse still, Mr Ritz has been so busy preparing for the grand opening that he has not been outside in days, and has no idea of the current time in Paris, nor anywhere else in the world. All he knows about each city is its time difference from Paris, in equally precise detail.
Help Mr Ritz save face by labelling the clocks in a way that is consistent with the time differences.
The first line of input consists of a single integer $n$ ($1 \le n \le 1000$).
$n$ lines follow, the $i$th consisting of three two-digit colon-separated integers $h_i$ ($0 \le h_i \le 23$), $m_i$ ($0 \le m_i \le 59$) and $s_i$ ($0 \le s_i \le 59$), representing the hours, minutes and seconds displayed on the $i$th clock. No two of these lines are identical.
The last line of input consists of $n$ space-separated integers $d_1, \ldots, d_n$ ($-43199 \le d_j \le 43200$), the $j$th of these representing the time difference from Paris to the $j$th city in seconds. No two of the $d_j$ are equal.
If there is no valid labelling of the clocks, output "Impossible" (without punctuation).
Otherwise, output a single line containing $n$ space-separated integers, the city numbers corresponding to the clocks. There may be several correct solutions; any labelling of clocks which is consistent with the time differences will be accepted.
Input
The first line of input consists of a single integer $n$ ($1 \le n \le 1000$).
$n$ lines follow, the $i$th consisting of three two-digit colon-separated integers $h_i$ ($0 \le h_i \le 23$), $m_i$ ($0 \le m_i \le 59$) and $s_i$ ($0 \le s_i \le 59$), representing the hours, minutes and seconds displayed on the $i$th clock. No two of these lines are identical.
The last line of input consists of $n$ space-separated integers $d_1, \ldots, d_n$ ($-43199 \le d_j \le 43200$), the $j$th of these representing the time difference from Paris to the $j$th city in seconds. No two of the $d_j$ are equal.
Output
If there is no valid labelling of the clocks, output "Impossible" (without punctuation).
Otherwise, output a single line containing $n$ space-separated integers, the city numbers corresponding to the clocks. There may be several correct solutions; any labelling of clocks which is consistent with the time differences will be accepted.
4
06:00:00
04:00:00
10:00:00
01:00:00
7800 600 -10200 22200
4
06:00:00
10:00:00
04:00:00
01:00:00
7800 600 -10200 22200
3
11:59:59
12:00:00
12:00:02
1 0 -2
2
00:00:00
23:59:59
0 1
2
00:00:00
12:00:00
0 43200
1 2 4 3
1 4 2 3
Impossible
2 1
1 2
Note
In the first sample input, the time in Paris is 03:50:00. Then the times in all cities are consistent:
- The time in city 1 (06:00:00) is 7800 seconds (2 hours 10 minutes) ahead of Paris time
- The time in city 2 (04:00:00) is 600 seconds (10 minutes) ahead of Paris time
- The time in city 3 (10:00:00) is 22200 seconds (6 hours 10 minutes) ahead of Paris time
- The time in city 4 (01:00:00) is 10200 seconds (2 hours 50 minutes) behind of Paris time
The second sample case is intended to clarify the output format further. 4 in the second position indicates that the second clock matches the fourth difference, not that the fourth clock matches the second time difference.
In the third sample input, the time differences from Paris are not consistent with the clock times.
In the fourth sample input, the time in Paris is 23:59:59. Then the times in all cities are consistent:
- The time in city 1 (00:00:00) is 1 second ahead of Paris time
- The time in city 2 (23:59:59) is in sync with Paris time
In the fifth sample input, the time in Paris could be midnight or midday. Either way, the times in both cities are consistent.