有一个长字符串 $S$，其中每个字符都是小写英文字母。

两位男孩 Hyosong 和 Gwangsong 正在玩一个有趣的游戏。游戏规则如下：

最初，裁判 Hakmyong 给他们一个 $S$ 的非空子串（记为 $P$）。

两位玩家轮流在子串后添加一个英文字母，使得结果字符串仍然是 $S$ 的子串。如果无法添加任何字符，游戏结束。

Hyosong 希望最终字符串尽可能短，而 Gwangsong 希望最终字符串尽可能长。Hyosong 先手。

如果他们都采取最优策略，你可以推断出每个子串对应的“添加字符数”（记为 $f(P)$）。

子串 $A$ 小于子串 $B$，当且仅当 $f(A) < f(B)$ 成立，或者 $f(A) = f(B)$ 且 $A$ 在字典序上小于 $B$。

给定整数 $K$，你必须找出 $S$ 的第 $K$ 小的子串。你能找出来吗？

输入格式

第一行包含一个字符串，其长度小于或等于 $500000$。 第二行包含一个整数 $K$ ($1 \le K \le 1000000000$)。

输出格式

输出最终子串的添加字符数和最终子串，中间用空格隔开。

样例

输入 1

aababb
8

输出 1

1 abab