using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("eel");
WillReturn.Add("6");
//Eel
}
else if (InputPattern == "Input2") {
WillReturn.Add("lexicographical");
WillReturn.Add("100");
//capal
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static string mS;
static int UB;
static long mK;
// 登場する文字の配列
static char[] mCharArr;
static void Main()
{
List<string> InputList = GetInputList();
mS = InputList[0];
mK = long.Parse(InputList[1]);
string Answer = Solve();
Console.WriteLine(Answer);
}
static string Solve()
{
// 空文字の分
mK++;
// 始点ノードと終点ノードを追加
mS = "S" + mS + "E";
UB = mS.Length - 1;
// 手順01 文字ごとのIndのListを作成
CreateCharIndList();
// 手順02 DPを実行
ExecDP();
// 手順03 DP結果から解を求める
string Answer = DeriveAnswer();
return Answer;
}
// 手順01 文字ごとのIndの配列を作成
static Dictionary<char, int[]> mIndArrDict;
static void CreateCharIndList()
{
mCharArr = mS.ToCharArray().Distinct().OrderBy(pX => pX).ToArray();
var IndListDict = new Dictionary<char, List<int>>();
for (int I = 0; I <= UB; I++) {
char CurrChar = mS[I];
if (IndListDict.ContainsKey(CurrChar) == false) {
IndListDict[CurrChar] = new List<int>();
}
IndListDict[CurrChar].Add(I);
}
mIndArrDict = new Dictionary<char, int[]>();
foreach (var EachPair in IndListDict) {
mIndArrDict[EachPair.Key] = EachPair.Value.ToArray();
}
}
// 終点ノードまでの経路数[現在ノード]なDP表
static long[] mDPArr;
// 手順02 DPを実行
static void ExecDP()
{
mDPArr = new long[UB + 1];
mDPArr[UB] = 1; // 終点ノードに1を設定し、逆辺を使って配るインラインDP
var OverFlowNodeSet = new HashSet<long>();
for (int I = UB; 0 <= I; I--) {
if (mDPArr[I] == 0) continue;
if (OverFlowNodeSet.Contains(I)) continue;
// 同じ文字の逆辺
int ResultInd1 = ExecNibunhou_LowerMax(I, mIndArrDict[mS[I]]);
int TargetInd1 = -1;
if (ResultInd1 > -1) {
TargetInd1 = mIndArrDict[mS[I]][ResultInd1];
if (WillOverAdd(mDPArr[TargetInd1], mDPArr[I], long.MaxValue)) {
mDPArr[TargetInd1] = long.MaxValue;
OverFlowNodeSet.Add(TargetInd1);
}
else {
mDPArr[TargetInd1] += mDPArr[I];
}
}
// 違う文字の逆辺
foreach (char EachChar in mCharArr) {
if (EachChar == mS[I]) continue;
int ResultInd2 = ExecNibunhou_LowerMax(I, mIndArrDict[EachChar]);
if (ResultInd2 == -1) continue;
for (int J = ResultInd2; 0 <= J; J--) {
int TargetInd2 = mIndArrDict[EachChar][J];
if (TargetInd1 > -1) {
if (TargetInd2 < TargetInd1) {
break;
}
}
if (WillOverAdd(mDPArr[TargetInd2], mDPArr[I], long.MaxValue)) {
mDPArr[TargetInd2] = long.MaxValue;
OverFlowNodeSet.Add(TargetInd2);
}
else {
mDPArr[TargetInd2] += mDPArr[I];
}
}
}
}
}
// 二分法で、Val未満で最大の値を持つ、添字を返す
static int ExecNibunhou_LowerMax(int pVal, int[] pArr)
{
if (pArr.Length == 0) return -1;
// 最後の要素がVal未満の特殊ケース
if (pVal > pArr.Last()) {
return pArr.GetUpperBound(0);
}
// 最初の要素がVal以上の特殊ケース
if (pVal <= pArr[0]) {
return -1;
}
int L = 0;
int R = pArr.GetUpperBound(0);
while (L + 1 < R) {
int Mid = (L + R) / 2;
if (pArr[Mid] < pVal) {
L = Mid;
}
else {
R = Mid;
}
}
return L;
}
// 二分法で、Val超えで最小の値を持つ、添字を返す
static int ExecNibunhou_UpperBound(int pVal, int[] pArr)
{
if (pArr.Length == 0) return -1;
// 最後の要素がVal以下の特殊ケース
if (pVal >= pArr.Last()) {
return -1;
}
// 最初の要素がVal超えの特殊ケース
if (pVal < pArr[0]) {
return 0;
}
int L = 0;
int R = pArr.GetUpperBound(0);
while (L + 1 < R) {
int Mid = (L + R) / 2;
if (pArr[Mid] > pVal) {
R = Mid;
}
else {
L = Mid;
}
}
return R;
}
struct JyoutaiDef
{
internal int CurrInd;
internal long CurrK;
}
// 手順03 DP結果から解を求める
static string DeriveAnswer()
{
if (mK > mDPArr[0]) return "Eel";
if (mK == 2) {
return mCharArr.Where(pX => pX != 'S' && pX != 'E').Min().ToString();
}
var Stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.CurrInd = 0;
WillPush.CurrK = mK;
Stk.Push(WillPush);
var sb = new System.Text.StringBuilder();
while (Stk.Count > 0) {
JyoutaiDef Popped = Stk.Pop();
if (Popped.CurrK == 1) {
break;
}
foreach (PathInfoDef EachInfo in DeriveAnswerHelper(Popped.CurrInd)) {
if (Popped.CurrK - EachInfo.PatternCnt <= 1) {
sb.Append(mS[EachInfo.CurrInd]);
WillPush.CurrInd = EachInfo.CurrInd;
WillPush.CurrK = Popped.CurrK - 1;
Stk.Push(WillPush);
break;
}
Popped.CurrK -= EachInfo.PatternCnt;
}
}
return sb.ToString();
}
// 現在の添字を指定して、次のノードまでの経路情報の列挙を返す
struct PathInfoDef
{
internal int CurrInd;
internal long PatternCnt;
}
static IEnumerable<PathInfoDef> DeriveAnswerHelper(int pCurrInd)
{
// 後続の1文字でループ
foreach (char EachKouho in mCharArr) {
if (EachKouho == 'S') continue;
if (EachKouho == 'E') continue;
int UpperB = ExecNibunhou_UpperBound(pCurrInd, mIndArrDict[EachKouho]);
if (UpperB > -1) {
int TargetInd = mIndArrDict[EachKouho][UpperB];
PathInfoDef WillReturn;
WillReturn.CurrInd = TargetInd;
WillReturn.PatternCnt = mDPArr[TargetInd];
yield return WillReturn;
}
}
}
// 2つの非負整数の足し算が、Limitを超えるかを返す
static bool WillOverAdd(long pA, long pB, long pLimit)
{
return pA > pLimit - pB;
}
}