Going in Circles on Alpha Centauri

In the early 27th century, Alpha Centauri has become the main shipping hub for this part of the galaxy. At a space station near the fourth planet, goods from almost every space-faring civilization are traded and shipped to every major star system. The station is a large ring, and its outer rim carries docking ports numbered clockwise from 1 to n.

When a trading spaceship docks at a port, it usually asks for its cargo to be moved to another ship docked at a different port. Transportation robots (transrobs) operating inside the ring do this work. Transrobs travel clockwise around the station and load and unload cargo at the ports.

Every ship's cargo fits into a single transport container, and each transrob carries at most one container at a time. The transrobs differ only in the maximum weight they can carry.

The consortium that runs the station wants performance statistics before upgrading the system. Specifically, they want:

• the average time needed to fulfil a request, i.e. the time from when a ship requests a delivery until the cargo is actually delivered to its destination; and
• the utilization of the transrobs, i.e. the average fraction of transrobs that are servicing requests during a given interval of time.

You must write the simulation program. The transrob control program works as follows:

• The transrobs are numbered 1 to m.
• Moving from one port to the next takes 1 minute; loading or unloading a container takes 5 minutes.
• Transrobs run on separate tracks and never hinder one another.
• A transrob is either idle or servicing a request. Servicing a request means: move to the request's origin, load the cargo, move to the destination, unload the cargo, and become idle again.
• Every incoming request is placed on the request list. A request can be satisfied if there is an idle transrob whose capacity is at least the cargo's weight.
• As long as (and as soon as) the list holds a request that can be satisfied, requests are assigned to transrobs, giving priority to older requests over newer ones. Each request is assigned to the idle, capable transrob that is closest to the request's origin in the anti-clockwise direction (equivalently, the transrob needing the fewest clockwise steps to reach the origin). If two transrobs are equally close, the one with the smaller number is chosen. An assigned request is removed from the list.
• Assignment is instantaneous: a transrob starts moving the instant it is assigned a request, and it becomes idle (and eligible for a new request) the instant it finishes unloading.

At time 0, every transrob is idle and located at port 1.

The input contains several simulations. Each simulation begins with a line holding two integers n and m, the number of ports and the number of transrobs, with 2 ≤ n ≤ 100 and 1 ≤ m ≤ 20. The next m lines each contain one integer l_i, the maximum load transrob i can carry, measured in galactic tons.

Then come one or more shipment requests. Each request is a line with four integers t, o, d, w: the time t (in minutes since the start of the simulation) at which the request is made, the origin port o, the destination port d, and the container weight w in galactic tons. Request times are strictly increasing within a simulation. The values satisfy 1 ≤ t, 1 ≤ o, d ≤ n, o ≠ d, and 1 ≤ w ≤ max{ l_i : 1 ≤ i ≤ m }. The list of requests ends with the line “-1 -1 -1 -1”.

The input ends with a simulation whose first line is “0 0”; do not process it.

For each simulation, first print a line “Simulation X”, where X counts the simulations starting from 1. Then print exactly two lines in this format:

Average wait time   = A minutes
Average utilization = B %

A is the average wait time over all requests, where a request's wait time is the interval from when it was made until its cargo is delivered (the moment unloading finishes). B is the utilization percentage over the interval from the moment the first request is made until the moment the last request is delivered; it equals the average number of busy transrobs during that interval, divided by m, times 100.

Both A and B are printed with exactly three digits after the decimal point, using the spacing shown above. Separate the output of consecutive simulations with a blank line.