Multilevel Feedback Queue

The story

A plain Round Robin scheduler treats a quick keystroke handler and a week-long simulation the same. The Multilevel Feedback Queue (MLFQ) fixes that without knowing the job lengths in advance: every new job starts in the top queue with a short time slice. A job that uses its whole slice and still wants more is probably CPU-bound, so it is demoted to a lower queue with a longer slice; a job that finishes early stays responsive. The CPU always serves the highest non-empty queue first.

You are asked to simulate a small MLFQ and report how long each job waited.

The rules

There are k queues, numbered 0 (top, highest priority) to k-1 (bottom). Queue i has the time quantum q[i]. Every process has an arrival time and a CPU burst (no I/O). Time is in whole units.

1. A process enters queue 0 at its arrival time. Processes with the same arrival time enter in input order.
2. Whenever the CPU is free, it takes the first process of the highest-priority non-empty queue (queues are FIFO) and runs it for min(q[level], remaining burst) units. Nothing interrupts a slice: a process that arrives meanwhile has to wait for it to end.
3. When a slice ends at time t:
   • first, every process with arrival <= t that has not entered yet is added to queue 0;
   • then, if the running process finished, record finish = t; otherwise it used its whole quantum, so it moves to the tail of the next queue down (a process in the bottom queue goes back to the tail of the bottom queue).
4. If every queue is empty, the CPU idles until the next arrival.

waiting = finish - arrival - burst.

Input and output

Input: k; then the k quanta on one line; then n; then n lines name arrival burst (integers, burst >= 1; names have no spaces; the lines are in any order).

Output: one line name finish waiting per process in input order, then a last line average_wait <value> with the average waiting time to two decimals (the checker allows a tolerance of half a cent).

Example

3
2 4 8
3
A 0 7
B 1 3
C 2 1

Output:

A 11 4
B 10 6
C 5 2
average_wait 4.00

How it unfolds: A runs alone at first and uses its whole quantum of 2 (time 0 to 2); B and C have arrived by then, so they join queue 0 and A drops to queue 1. B runs 2 to 4 and drops. C needs only 1 unit and finishes at 5. Queue 0 is empty, so queue 1 is served: A runs 5 to 9 (quantum 4) and drops to queue 2, B runs its last unit from 9 to 10, and A finishes its last unit at 11.

3
2 4 8
3
A 0 7
B 1 3
C 2 1