Lexicographically largest output from a spreading availability mask

A test-data service builds an output array S from two inputs:

• arr, an array of n positive integers;
• state, a string of length n made of '0' and '1'. state[i] = '1' means arr[i] is available; '0' means it is blocked.

The service runs exactly m operations. In each operation:

1. Choose any available index i and append arr[i] to S. The element is not consumed; it stays available and may be chosen again later.
2. Then every blocked index i with state[i - 1] = '1' becomes available. All of these updates use the state from before this step, so availability moves at most one cell to the right per operation.

Implement:

def generate_array(arr: list[int], state: str, m: int) -> list[int]:
    ...

Return the lexicographically largest S the service can produce.

Constraints

• 1 <= n <= 10^5, 0 <= m <= 10^5
• 1 <= arr[i] <= 10^9
• state contains at least one '1'

Example 1

arr = [3, 8, 2, 9, 4], state = "10000", m = 4
output: [3, 8, 8, 9]

Only index 0 starts available, so the first pick is 3. After that, index 1 unlocks (8), then index 2 (2), then index 3 (9). The best value available at each step is 3, 8, 8, 9.

Example 2

arr = [7, 1, 5, 2], state = "0010", m = 3
output: [5, 5, 5]

Availability only spreads to the right, so 7 and 1 are never reachable. Index 3 unlocks after the first step, but 2 never beats 5.