컴퓨터 DJ

시간 제한1초메모리 제한128 MB

요약
A부터 Z까지의 문자로 이루어진 모든 단어를 길이순, 사전순으로 이어 붙인 무한 문자열에서 k번째 문자에 대응하는 곡 제목을 찾는다.
난이도

보통10점 중 5점

유형
수학, 조합론, 구현, 완전 탐색
정답자
아직 제출이 없습니다

문제

어느 유명한 DJ가 컴퓨터 과학 학회의 폐막 파티에서 음악을 틀어 달라는 초청을 받았습니다. 참가자들에게 깊은 인상을 주려고 그는 파티에서 틀 곡을 프로그램으로 고르기로 했습니다. 그런데 프로그램이 곡을 고르는 방식이 몹시 이상하고 반복적이어서 결과는 엉망이었습니다.

먼저 DJ는 보유한 곡 중에서 NN개의 곡을 골랐습니다. 프로그램은 각 곡에 'A'부터 'Z'까지 서로 다른 문자 하나를 이름표로 붙입니다. ii번째 곡에는 'A'-'Z' 순서의 ii번째 문자가 붙습니다. 프로그램은 다음의 무한 문자열에서 이름표가 나타나는 순서대로 파티에서 틀 곡을 정합니다. 먼저 길이가 1인 모든 단어를 사전순으로, 그다음 길이가 2인 모든 단어를 사전순으로, 그다음 길이가 3인 모든 단어를 사전순으로, 이런 식으로 이어집니다. N=3N = 3이면 이 문자열은 다음과 같이 시작합니다: ABCAAABACBABBBCCACBCCAAAAABAACABAABBABC...

파티가 끝난 뒤 어떤 사람들은 DJ에게 처음 튼 곡이 무엇이었는지 물었습니다. 또 어떤 이들은 25번째로 튼 곡을 알고 싶어 했고, 그런 질문이 이어졌습니다. DJ는 곡이 반복되는 이 이상한 규칙 말고는 아무것도 기억하지 못하므로, 여러분에게 그런 질문에 답하는 프로그램을 만들어 달라고 부탁합니다.

입력

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 테스트 케이스는 세 줄로 구성됩니다. 첫째 줄에는 두 정수 NN과 QQ가 주어지며, 각각 DJ가 고른 곡의 수와 참가자들이 던진 질문의 수를 뜻합니다 (1≤N≤261 \le N \le 26, 1≤Q≤10001 \le Q \le 1000). 둘째 줄에는 NN개의 곡 제목이 공백 하나로 구분되어 주어집니다(곡 제목은 알파벳과 숫자로 이루어진 길이 1 이상 100 이하의 문자열입니다). 셋째 줄에는 질문들이 나열됩니다. 각 질문은 정수 kk (1≤k≤100 000 0001 \le k \le 100\,000\,000)로, 파티에서 kk번째로 튼 곡을 뜻합니다. 입력의 끝은 N=Q=0N = Q = 0으로 표시됩니다.

출력

각 테스트 케이스의 각 질문 kk에 대해, 파티에서 kk번째로 튼 곡의 제목을 한 줄에 하나씩 출력합니다. 각 테스트 케이스 뒤에는 빈 줄을 하나 출력합니다.

예제3

  1. 예제 1

    입력
    10 3
S0 S1 S2 S3 S4 S5 S6 S7 S8 S9
3 6 10
3 5
Pathethique TurkishMarch Winter
1 2 3 4 16
0 0
    예상 출력
    S2
S5
S9

Pathethique
TurkishMarch
Winter
Pathethique
Winter

  2. 예제 2

    입력
    2 7
Do Re
1 2 3 6 7 10 11
0 0
    예상 출력
    Do
Re
Do
Re
Re
Re
Do

  3. 예제 3

    입력
    3 3
X Y Z
21 22 100
0 0
    예상 출력
    Z
X
Z