16914번 - K번째 부분 문자열

문제

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

• K: S의 서로 다른 부분 문자열을 사전 순으로 정렬했을 때, K번째 오는 문자열을 출력한다.

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

입력

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

출력

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

제한

• 1 ≤ S의 길이 ≤ 90,000
• 1 ≤ Q ≤ 500
• 0 < K < 2³¹

힌트