Extend the payroll system to support settlements.
Each driver has a unique string `driver_id` and a fixed `hourly_rate`. You are given a list of operations to process in order.
Supported operations:
- `('register_driver', driver_id, hourly_rate)` — add a new driver.
- `('record_shift', driver_id, start_ts, end_ts)` — record one completed shift. The shift's pay is `hourly_rate * (end_ts - start_ts) / 3600`.
- `('settle_up_to', cutoff_ts)` — mark as paid every shift whose `end_ts <= cutoff_ts`.
- `('get_unpaid_balance', driver_id)` — return how much money is still unpaid for that driver.
Return the results of all `get_unpaid_balance` operations in the order they appear.
Your implementation should support settlement efficiently even when there are many historical shifts. Avoid scanning all recorded shifts on every settlement.
All operations are valid:
- a driver is registered before any shift/query for that driver,
- each `driver_id` is registered once,
- `end_ts > start_ts`.
Examples
Input: [('register_driver', 'd1', 20), ('record_shift', 'd1', 0, 3600), ('record_shift', 'd1', 3600, 10800), ('get_unpaid_balance', 'd1'), ('settle_up_to', 4000), ('get_unpaid_balance', 'd1'), ('settle_up_to', 20000), ('get_unpaid_balance', 'd1')]
Expected Output: [60.0, 40.0, 0.0]
Explanation: Before any settlement, both shifts are unpaid for a total of 60. After settling up to 4000, only the first shift is paid. After settling up to 20000, both are paid.
Input: [('register_driver', 'd1', 10), ('register_driver', 'd2', 30), ('record_shift', 'd1', 0, 7200), ('record_shift', 'd2', 0, 3600), ('settle_up_to', 5000), ('get_unpaid_balance', 'd1'), ('get_unpaid_balance', 'd2'), ('record_shift', 'd2', 3600, 7200), ('get_unpaid_balance', 'd2'), ('settle_up_to', 8000), ('get_unpaid_balance', 'd1'), ('get_unpaid_balance', 'd2')]
Expected Output: [20.0, 0.0, 30.0, 0.0, 0.0]
Explanation: The first settlement pays only d2's first shift. Later, after another d2 shift is recorded and settlement reaches 8000, all remaining unpaid shifts are paid.
Input: [('register_driver', 'empty', 25), ('settle_up_to', 100000), ('get_unpaid_balance', 'empty')]
Expected Output: [0.0]
Explanation: Edge case: a driver with no shifts has unpaid balance 0, even after settlement.
Input: [('register_driver', 'x', 10), ('record_shift', 'x', 0, 3600), ('settle_up_to', 5000), ('get_unpaid_balance', 'x'), ('settle_up_to', 1000), ('get_unpaid_balance', 'x')]
Expected Output: [0.0, 0.0]
Explanation: A shift should not be paid twice. A later settlement with a smaller cutoff changes nothing.