← 返回题目列表

AtCoder · tdpc_lexicographical

G. 辞书顺

中文机器翻译题面 查看原题

问题陈述

文字列 s 在非空子序列中,按字典序 K 求第x个。若不存在这样的子序列,则输出“鳗鱼”(为清楚起见而引用)。
但是, 运算前设定中包含的s 从某个字符串中去掉若干个字符(可以是0个字符),剩下的字符按原顺序连接起来的称为子序列。例如,"aba" 的子序列有 "a"、"b"、"aa"、"ab"、"ba"、"aba" 共6个。"a" 虽然在不同位置出现两次,但作为字符串相同的子序列不区分。

约束

  • 1 ≤ |s| ≤ 1000000
  • s 中的每个字符都是小写字母 ('a'-'z')。
  • 1 ≤ K ≤ 10^{18}

输入格式

输入是按以下格式从标准输入给出的。
s
K

输出格式

请将答案输出为一行。

示例输入 1

eel
6

示例输出 1

Eel
"eel" 的子序列按字典顺序为 e、ee、eel、el、l。第6个子序列不存在。

示例输入 2

lexicographical
100

示例输出 2

capal