题目描述

美国计算机安全办公室声称，如果没有调度程序的帮助，9月11日的恐怖袭击不可能同时劫持4架飞机并撞击目标大楼。为了验证这一说法，信息部决定编写一个类似的程序，并检查程序结果是否与9月11日的劫持计划一致。恐怖分子的计划是劫持一些刚起飞的飞机，并立即转向撞击目标大楼。每架被劫持的飞机最多只能用于撞击一座大楼。程序的输入包括航班调度信息和美国主要大楼的位置。假设恐怖分子希望至少摧毁d座大楼，并且希望最小化第一座和最后一座大楼被撞击的时间间隔。

输入格式

输入包含多个测试用例。每个测试用例的第一行包含4个数字n、k、p、d，分别表示机场数量、大楼数量、飞机数量和至少需要摧毁的大楼数量。接下来的n行每行包含两个整数x和y，表示第i个机场的坐标。随后的k行每行包含两个整数x和y，表示第i座大楼的坐标。最后的p行每行包含5个整数h、m、f、t、s，表示第i架飞机于h时m分从机场f飞往机场t，速度为每秒s公里。当n=k=p=d=0时表示输入结束。所有坐标单位为公里。（n≤50，k≤50，p≤90）

输出格式

对于每个测试用例（除n=k=p=d=0的情况），输出一行表示至少摧毁d座大楼时，第一座和最后一座大楼被撞击的最小时间间隔（格式为h:m）。如果时间间隔包含秒数，则四舍五入到分钟。如果无法满足条件，则输出"Impossible!"。

示例输入与输出

输入数据 1

2 2 2 2
17 97
25 47
72 7
43 78
18 41 1 2 4
7 17 1 2 8
2 1 1 1
89 85
57 45
2 25
14 5 2 1 7
0 0 0 0

输出数据 1

11:24
0:0

来源

Tehran Sharif Local Contest 2001