노랫말

현대 노랫말의 정보량이 그다지 많지 않다는 것은 잘 알려져 있다. (http://en.wikipedia.org/wiki/The_Complexity_of_Songs) 각 변수가 문자열 또는 앞서 나온 두 변수의 결합에 해당하도록 변수들의 모음으로 텍스트를 나타낼 수 있다. 최종 텍스트는 마지막 변수의 값으로 주어진다.

PO 운영진은 이제 $Q$개의 서로 다른 $R$ 값 각각에 대해 노랫말의 $R$:번째 문자가 무엇인지 알고 싶어 한다.

채점

여러 테스트 케이스 그룹으로 해답을 테스트한다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한

$1$ | $20$ | $N \leq 5\,000$, $Q \leq 10\,000$, 만들어지는 문자열의 길이는 $10^{18}$자보다 짧다

$2$ | $60$ | 만들어지는 문자열의 길이는 $10^{18}$자보다 짧다

$3$ | $20$ | 추가 제한 없음

첫째 줄에 두 정수 $N$ ($1 \leq N \leq 500\,000$)와 $Q$ ($1 \leq Q \leq 80\,000$)가 주어진다.

이어서 $N$개의 줄이 주어지며, 각 줄에는 다음 두 형식 중 하나가 주어진다.

• 영 하나와 그 뒤에 단어 하나: 0 <ett ord> (단어의 문자는 최대 $10$개이며, a-z만 사용)로, 변수가 단순한 단어를 나타내는 경우이다.

• 두 정수 A와 B로, 이어 붙일 문자열들의 번호 ($1 \leq A, B <$ 현재 줄 번호)이다. 즉, 앞서 나온 두 단어를 이어 붙여 만든 단어이다.

그다음에는 각 줄에 정수 $R$가 하나씩 있는 $Q$개의 줄이 주어진다. ($1 \leq R \leq \min(10^{18},$ 문자열의 길이$))$, 관심 있는 문자들의 번호이다.

요청된 $Q$개의 문자를 한 줄에 출력한다.

먼저 단어 "hej"를 얻는다. 그다음 이 단어를 자기 자신과 이어 붙이는 줄이 나오므로, 이제 "hejhej"를 얻는다. 문자열의 $3$번째 문자와 $4$번째 문자는 "jh"이다.