앨리스와 밥 (그리고 문자열): Double Menace

앨리스와 밥이 게임을 한다. 처음에 문자열 $s$와 $s$의 부분 문자열 $t$가 주어진다. 각 차례에 플레이어는 임의의 소문자 $c_l$을 $t$의 왼쪽에, 임의의 소문자 $c_r$을 $t$의 오른쪽에 붙인다. 이때 $t$가 여전히 $s$의 부분 문자열이어야 한다. 유효한 수를 둘 수 없는 플레이어가 진다. 앨리스가 먼저 둔다.

앨리스는 첫 수를 두기 전에 초기 문자열 $t$를 고를 수 있다. 두 플레이어가 최선을 다한다고 가정할 때 앨리스가 이기는 것이 보장되는 $t$를 고르려 한다. 밥이 눈치채지 않도록, 이기는 초기 문자열 중 사전순으로 $k$번째로 작은 문자열을 고른다. 앨리스를 도와라.

첫 줄에 소문자 영어 알파벳으로 이루어진 문자열 $s$가 주어진다 ($1 \leq |s| \leq 10^5$).

둘째 줄에 정수 $k$가 주어진다 ($1 \leq k \leq 10^{10}$).

이기는 초기 문자열이 $k$개보다 적으면 "no solution"을 출력한다. 그렇지 않으면 사전순으로 $k$번째인 이기는 초기 문자열을 출력한다. 그 문자열이 빈 문자열이면 "-"를 출력한다.

$s=\mathtt{abac}$일 때 이기는 문자열은 -, a, b, ba이다.