G - 辞書順 解説 /

実行時間制限: 2 sec / メモリ制限: 256 MB

Problem Statement

文字列 s の空でない部分列のうち、辞書順で K 番目のものを求めよ。そのようなものが存在しない場合は "Eel" (quotes for clarity) と出力せよ。

ただし、s から何文字か取り除き (0 文字でもよい)、残りの文字を順番を変えずにつなげたものを部分列という。たとえば、"aba" の部分列は "a", "b", "aa", "ab", "ba", "aba" の 6 個である。"a" は異なる場所に二回現れるが、文字列として同じであれば区別しないものとする。

Constraints

  • 1 ≤ |s| ≤ 1000000
  • Each character in s will be a lowercase letter ('a'-'z').
  • 1 ≤ K ≤ 10^{18}

Input Format

入力は以下の形式で標準入力から与えられる。
s
K

Output Format

答えを一行に出力せよ。

Sample Input 1

eel
6

Sample Output 1

Eel
eel の部分列は辞書順に e, ee, eel, el, l である。6 番目は存在しない。

Sample Input 2

lexicographical
100

Sample Output 2

capal