IntermediateSimulation & Finance25 points

Check-in desks at Istanbul Airport

A check-in hall at Istanbul Airport has several desks and a single shared queue. Passengers are served first come, first served. Managers want to know how long people wait and how evenly the desks are used.

Task: line 1 is the number of desks k. Line 2 is the number of passengers n. Then n lines arrival service (integer minutes; the arrival times never decrease). All desks are free at minute 0. Passengers are processed in input order. A passenger picks the desk that can start serving them earliest: for desk j that moment is max(arrival, free_j), where free_j is when the desk finishes its current passenger. If several desks give the same moment, take the one with the lowest number (desks are numbered from 1). The wait is start - arrival. Print four lines: Average wait: X (2 decimals), Longest wait: Y, Served per desk: a b c ... (one count per desk, in desk order), and Closing time: T (the minute the last service ends).

Sample tests

Input

2
6
0 5
1 4
2 3
3 6
10 2
11 2

Expected output

Average wait: 0.83
Longest wait: 3
Served per desk: 3 3
Closing time: 13

Input

1
4
0 3
1 3
2 3
20 1

Expected output

Average wait: 1.50
Longest wait: 4
Served per desk: 4
Closing time: 21

Your answer is also checked against 3 hidden tests.