압축된 채팅 기록 조회

문제

게임 서버는 용량을 아끼기 위해 채팅 기록을 길이 압축해 저장한다. 압축 문자열 S는 소문자 하나 뒤에 반복 횟수를 나타내는 십진 정수가 붙은 덩어리를 이어 붙인 것이다. 예를 들어 a3b2a1은 aaabba를 뜻한다. 반복 횟수는 앞에 0이 붙지 않은 1 이상의 정수이며, 인접한 두 덩어리의 문자가 같을 수도 있다. 운영자는 압축을 풀지 않고 기록의 특정 위치에 있는 글자를 알고 싶어 한다. 압축을 풀었을 때의 문자열에서 위치는 1부터 센다. 위치 Q개가 주어질 때, 각 위치의 글자를 순서대로 출력하라. 압축을 풀었을 때의 전체 길이는 매우 길 수 있으므로 실제로 풀어서 저장해서는 안 된다. 주어지는 모든 위치는 1 이상이고 압축을 풀었을 때의 전체 길이 이하이다.

입력

첫 줄에 압축 문자열 S가 주어진다. 둘째 줄에 질의 수 Q가 주어진다. 셋째 줄에 위치 Q개가 공백으로 구분되어 주어진다. S의 길이는 2 이상 120000 이하이고, 각 덩어리의 반복 횟수는 1 이상 10^9 이하이다. 1 ≤ Q ≤ 20000이다.

출력

각 질의의 글자를 입력 순서대로 한 줄에 하나씩 출력한다.

a3b2a1
4
1 3 4 6

a
a
b
a

x1y12z1
3
2 13 14

y
y
z

출처: Devin.KR 자체 제작