A one-way lane is a string road of cells, traffic flowing to the right. Each cell is > (a car), . (empty) or # (a barrier that never moves and that cars cannot enter).
The lane changes in ticks. In one tick, every car looks at the cell directly to its right as it was at the start of the tick:
- if that cell is
., the car moves into it; - if the car is in the last cell of the road, it drives off the road and disappears;
- otherwise (the cell holds a car or a
#) the car stays where it is.
All cars decide and move at the same moment, so a car never moves into a cell that another car is leaving during the same tick. Return the road after t ticks.
Examples
Input: road = ">.>..#>.", t = 2
Output: "..>.>#.."
Explanation: the car in cell 6 drives off the end during the second tick.
Input: road = ">>>...#.>", t = 10
Output: "...>>>#.."
Constraints
1 <= len(road) <= 2 * 10**50 <= t <= 10**18- Target complexity: about O(len(road)). Simulating tick by tick is far too slow.
Goals
- Model a synchronous traffic rule exactly: a car moves only into a cell that was empty when the tick began
- Turn the tick rule into a closed formula for each car's position after t ticks
- Evaluate that formula for every car in linear time with a sliding-window minimum