Character at a Position in a Run-Length Encoded String Without Decoding

A sequence of characters has been stored with run-length encoding: each maximal run of one repeated character is written as the character followed by the run length. For example, the sequence `B, A, A, E, E, E, C` is stored as `"B1A2E3C1"`. Implement a lookup that, working from the encoded data, returns the character at position `p` of the original (decoded) sequence. The runs can be very long, so decoding the whole sequence is not an option. The console version answers a batch of positions in one call. ### Function Signature ```python def char_at_positions(encoded: str, positions: list[int]) -> list[str]: ``` ### Rules - `encoded` is a concatenation of runs. Each run is one uppercase English letter followed by its length written in decimal with no leading zeros. - Positions are 0-indexed into the decoded sequence. - Return one single-character string per query, in the same order as `positions`. ### Constraints - `1 <=` number of runs `<= 10^5` - Each run length is an integer in `[1, 10^9]`. - The decoded length (the sum of all run lengths) is at most `10^14`, which is below `2^53`. - `1 <= len(positions) <= 10^5` - `0 <= positions[j] <` decoded length. ### Examples **Example 1** - Input: `encoded = "B1A2E3C1"`, `positions = [0, 1, 2, 3, 5, 6]` - Output: `["B", "A", "A", "E", "E", "C"]` - Explanation: The decoded sequence is `B A A E E E C`, with positions 0 through 6. **Example 2** - Input: `encoded = "X1000000000Y1Z25"`, `positions = [999999999, 1000000000, 1000000001, 1000000025]` - Output: `["X", "Y", "Z", "Z"]` - Explanation: Positions 0 to 999999999 hold `X`, position 1000000000 holds `Y`, and positions 1000000001 to 1000000025 hold `Z`.