Decompression Queries

Version: Phuoc Hung OJ Extended

Problem Statement

An original string was run-length encoded: every maximal consecutive run of equal uppercase letters is represented by its letter followed by a positive integer count. The encoded string $E$ is therefore a sequence of letter-count pairs, and a count may contain multiple digits.

The original string may be too long to materialize in memory.

There are $Q$ queries. Query $i$ gives a 1-based position $p_i$ in the original string. Determine the character at that position for every query, then concatenate the answers in query order into a string of length $Q$.

Input

• Line 1 contains a valid encoded string $E$.
• Line 2 contains the positive integer $Q$.
• Line 3 contains $Q$ positive integers $p_1,p_2,\ldots,p_Q$. Every $p_i$ is at most the decompressed length.

Output

Print a string of exactly $Q$ characters. Its $i$-th character is the character at position $p_i$ in the original string.

Subtasks

• Subtask 1 (30 points): the decompressed length is at most $10^5$ and $Q\le10^3$.
• Subtask 2 (30 points): $Q\le10^3$.
• Subtask 3 (40 points): no additional restriction.
• In every subtask: $|E|\le10^6$, $Q\le2\cdot10^5$, and the decompressed length is at most $10^{18}$.

Examples

Input

A3B1C4D3A1
5
1 4 8 9 12

Output

ABCDA

Explanation

The encoded string represents AAABCCCCDDDA. Positions $1,4,8,9,12$ lie in the runs for A, B, C, D, and A respectively, so the answer is ABCDA.