The Two-Bank Cable Ferry

A cable ferry shuttles cars across a river between bank 'L' and bank 'R'. It carries at most capacity cars and every crossing takes crossing minutes. cars[i] = (arrival, bank) says car i reaches the dock on bank at minute arrival; cars is sorted by arrival time, and cars at the same bank board in list order. A car is waiting at minute T if it has arrived (arrival <= T) and has not been carried yet.

The ferry starts at bank 'L' at minute 0. Whenever it is docked at a bank at minute T:

1. If no car is waiting at either bank, it stays where it is until the next car arrives (or stops, if every car has been carried), and then applies these rules again.
2. Otherwise, if cars are waiting at its own bank, it loads the first capacity of them (or all of them if fewer) and crosses, arriving at minute T + crossing.
3. Otherwise (cars wait only on the other bank) it crosses empty, arriving at T + crossing.

Return a list whose entry i is the minute at which car i is unloaded on the far bank.

Examples

Input:  cars = [(0, 'L'), (0, 'L'), (0, 'L'), (5, 'R'), (40, 'R')], capacity = 2, crossing = 10
Output: [10, 10, 30, 20, 50]
Explanation: two cars cross at 0; at 10 the car waiting on R crosses back; at 20 the third car
leaves L; at 30 nobody waits, so the ferry idles on R until 40.

Input:  cars = [(3, 'R')], capacity = 1, crossing = 5
Output: [13]
Explanation: at minute 3 only bank R has a car, so the ferry crosses empty and returns with it.

Constraints

• 0 <= len(cars) <= 10**5, 1 <= capacity <= 10**5, 1 <= crossing <= 10**6
• 0 <= arrival <= 10**9, sorted in non-decreasing order
• Target: O(n) time, regardless of how large the minute values are

Goals

• Keep one FIFO queue per bank and admit cars as the clock passes their arrival times
• Jump the clock straight to the next event instead of ticking minute by minute
• Follow a precise rule set, including empty crossings and idle waiting