Truy vấn giải nén (Decompression Queries)

Phiên bản: Phước Hưng OJ Extended

Đề bài

Một xâu gốc đã được nén theo quy tắc: mỗi đoạn liên tiếp cực đại gồm các ký tự giống nhau được viết thành một chữ cái in hoa, sau đó là số lần xuất hiện của chữ cái đó. Xâu nén $E$ vì vậy gồm các cặp chữ cái-số đếm nối tiếp nhau; số đếm là số nguyên dương và có thể có nhiều chữ số.

Xâu gốc có thể rất dài nên không thể luôn tạo toàn bộ xâu đã giải nén trong bộ nhớ.

Có $Q$ truy vấn. Truy vấn thứ $i$ cho vị trí $p_i$, với các vị trí của xâu gốc được đánh số từ $1$. Với mỗi truy vấn, cần xác định ký tự của xâu gốc tại vị trí $p_i$.

Hãy trả lời các truy vấn theo đúng thứ tự đã cho và ghép các ký tự nhận được thành một xâu có độ dài $Q$.

Input

• Dòng 1 chứa xâu nén hợp lệ $E$.
• Dòng 2 chứa số nguyên dương $Q$.
• Dòng 3 chứa $Q$ số nguyên dương $p_1,p_2,\ldots,p_Q$. Mỗi $p_i$ không vượt quá độ dài xâu gốc sau khi giải nén.

Output

In một xâu gồm đúng $Q$ ký tự. Ký tự thứ $i$ là ký tự của xâu gốc tại vị trí $p_i$.

Subtask

• Subtask 1 (30 điểm): độ dài xâu gốc không vượt quá $10^5$ và $Q \le 10^3$.
• Subtask 2 (30 điểm): $Q \le 10^3$.
• Subtask 3 (40 điểm): không có ràng buộc bổ sung.
• Trong mọi Subtask: $|E| \le 10^6$, $Q \le 2\cdot 10^5$, và độ dài xâu gốc sau khi giải nén không vượt quá $10^{18}$.

Ví dụ

Input

A3B1C4D3A1
5
1 4 8 9 12

Output

ABCDA

Giải thích

Xâu nén biểu diễn xâu gốc AAABCCCCDDDA.

• Vị trí $1$ thuộc đoạn AAA, nên ký tự là A.
• Vị trí $4$ là B.
• Vị trí $8$ thuộc đoạn CCCC, nên ký tự là C.
• Vị trí $9$ thuộc đoạn DDD, nên ký tự là D.
• Vị trí $12$ là A.

Ghép các ký tự theo thứ tự truy vấn ta được ABCDA.