Returns Chute Sorter

Simulate a library's book-return conveyor that drops each book into a bin by call number, with an overflow tray and staff emptying bins.

Every call number is one or more capital letters followed by a number, such as QA76 or Z5. Call numbers are ordered by their letters first (alphabetically, so Q comes before QA), and books with identical letters by their number as an integer (QA9 comes before QA76).

The conveyor has bins numbered from 0. Bin i takes every call number from bins[i][0] to bins[i][1], both ends included. Ranges never overlap. Each bin holds at most capacity books, and the overflow tray holds at most overflow_capacity. Events are processed in order:

• A book (the event is its call number) goes to the end of its bin. If the bin is full it goes to the end of the overflow tray instead; if that is full too, it goes to the reject tray. A book that fits no bin's range goes straight to the reject tray.
• "empty k" means staff carry away every book in bin k (add them to the cart list in the order they were in the bin). Then the overflow tray is scanned from its front; each book that belongs to bin k moves to the end of bin k, as long as the bin still has room. The other overflow books stay in place, in order.

Input: bins, a list of [low, high] call-number pairs; capacity and overflow_capacity, integers; events, a list of strings.

Output: a list with one list of call numbers per bin (in bin order, oldest first), followed by the overflow tray, the reject tray, and the cart list: len(bins) + 3 lists in total.