K번째 부분 문자열

시간 제한2초메모리 제한512 MB

요약

문자열 S가 주어질 때, 서로 다른 부분 문자열을 사전순으로 나열했을 때 K번째 부분 문자열을 묻는 질의에 답하고, 존재하지 않으면 -1을 출력한다.

문제

문자열 $S$ 가 주어졌을 때, 다음 쿼리를 수행하려고 한다.

$S =$ "aaa"인 경우 부분 문자열은 "a", "a", "a", "aa", "aa", "aaa"가 있고, 서로 다른 부분 문자열은 "a", "aa", "aaa"가 있다.

첫째 줄에 문자열 $S$ , 둘째 줄에 쿼리의 개수 $Q$ 가 주어진다. 다음 $Q$ 개의 줄에는 쿼리 $K$ 가 한 줄에 하나씩 주어진다.

각각의 쿼리마다 $S$ 의 서로 다른 부분 문자열 중 사전 순으로 $K$ 번째 오는 것을 한 줄에 하나씩 출력한다. $K$ 번째 부분 문자열이 없는 경우에는 -1을 출력한다.