问题描述

在27世纪初，半人马座α星已成为该星系区域的主要货运枢纽。在第四颗行星附近的空间站中，几乎所有星际文明的货物都在此交易并运往各大恒星系统。空间站呈大圆形，外围有编号1至n的对接港口（顺时针方向）。

当贸易飞船停靠港口时，通常会请求将其货物转运至其他港口的另一艘飞船。这一任务由空间站环形轨道内的运输机器人（transrobs）负责。运输机器人可顺时针绕行空间站，并在港口装卸货物。

每艘飞船的货物恰好装入一个运输容器，所有运输机器人一次只能携带一个容器。运输机器人仅在最大载重量上有所不同。

空间站运营联盟最近决定升级其运输系统。但在升级前，他们希望收集当前系统性能的统计数据，具体关注：

1. 请求完成的平均时间，即从飞船请求将货物运往另一港口到货物实际送达目的地的时间。
2. 运输机器人的利用率，即在某时间段内服务请求的运输机器人的平均百分比。

为此，他们需要一个模拟程序，而你需要编写该程序。为简化任务，联盟提供了其运输机器人控制程序的以下细节：

• 运输机器人编号为1至m。
• 运输机器人从一个港口到下一个港口需1分钟，装卸容器各需5分钟。
• 运输机器人在不同轨道上运行，互不干扰。
• 运输机器人要么空闲，要么正在服务请求（即前往请求来源港口、装载货物、前往目的地港口、卸载货物，然后恢复空闲）。
• 所有新请求加入请求列表。若存在空闲且能承载货物重量的运输机器人，则请求可被满足。
• 只要（或一旦）请求列表中存在可满足的请求，就会将其分配给运输机器人，优先处理较早的请求。每个请求分配给逆时针方向距离请求来源港口最近的空闲且能承载的运输机器人；若距离相同，则编号较小的优先。分配后，请求从列表中删除。
• 分配过程瞬时完成（即机器人立即开始移动，卸载完成后立即恢复空闲）。

输入格式

输入包含多个需模拟的场景。每个场景首行为两个整数n和m（2 ≤ n ≤ 100，1 ≤ m ≤ 20），分别表示港口数量和运输机器人数量。随后m行每行一个整数li，表示运输机器人i的最大载重量（单位：银河吨）。

接下来是一个或多个运输请求。每个请求占一行，包含四个整数t、o、d、w：请求时间t（模拟开始后的分钟数）、来源港口o、目的地港口d、容器重量w。请求时间严格递增。取值范围：1 ≤ t，1 ≤ o, d ≤ n，o ≠ d，1 ≤ w ≤ max{li | 1 ≤ i ≤ m}。

运输请求描述以“-1 -1 -1 -1”结束。输入以n = m = 0终止，该场景无需处理。

输出格式

对每个场景，首先输出场景编号。随后模拟运输机器人对请求的处理，并输出平均等待时间和利用率百分比。利用率统计区间为从首个请求发出到所有请求完成的时间段。

模拟开始时（时间0），所有运输机器人空闲且位于1号港口。

所有数值需保留三位小数。每个测试用例后输出空行。

示例输入

10 3
5
10
20
1 2 9 8
2 7 8 5
5 3 2 17
20 1 2 4
-1 -1 -1 -1
0 0

示例输出

Simulation 1
Average wait time   = 17.250 minutes
Average utilization = 71.875 %

来源

1998年西南欧区域赛（Southwestern European Regional Contest）