Bank Tellers

A bank has tellers tellers and one waiting line. customers lists everyone who comes in, as tuples (arrive, work, patience, vip), sorted by arrive, a whole number of minutes. Serving a customer takes work minutes: a customer whose service starts at minute s is done at minute s + work, and their teller is free again at that minute.

• All tellers are free at the start, and each teller serves one customer at a time.
• A VIP customer (vip is True) joins the line behind the VIP customers already waiting, but in front of every regular customer. A regular customer joins at the back.
• Whenever a teller is free and someone is waiting, the customer at the front of the line goes to that teller.
• A customer who is still waiting patience minutes after arriving gives up and leaves the bank, unless a teller is free at that very minute.
• Everything that happens in the same minute happens in this order: tellers who are done become free, arriving customers join the line (in list order), free tellers take customers from the front of the line, and then customers whose patience has run out leave.

Write waits(tellers, customers) that returns a list with each customer's wait, the minute their service started minus the minute they arrived, in the same order as customers. Customers who gave up get -1.

Examples

waits(1, [(0, 5, 10, False), (1, 3, 10, False), (2, 2, 10, True)])
# returns [0, 6, 3]

waits(1, [(0, 5, 10, False), (1, 3, 2, False)])
# returns [0, -1]

waits(1, [(0, 3, 0, False), (1, 2, 2, False)])
# returns [0, 2]

In the first example the VIP who arrives at minute 2 goes ahead of the regular customer who arrived at minute 1, and is served at minute 5. In the second, the second customer gives up at minute 3, long before the teller is free. In the third, the teller becomes free at minute 3, the very minute the second customer's patience runs out, so they are served.

Constraints

• 1 <= tellers <= 100; customers has 0 to 100,000 tuples.
• 0 <= arrive <= 10**9, 1 <= work <= 10**6, 0 <= patience <= 10**9.