本评测链接与原题在数据范围进行微调，取消了单一词汇的长度限制，增加了词汇长度总和的限制。

时间限制： 1.5 秒

空间限制： 512 MB

题目背景

西西艾弗岛大数据中心正在如火如荼地开展大语言模型的研究工作。众所周知，计算机在执行机器学习的任务时，更适合处理数字的数据。对于大语言文本的处理， 最好的方式是将文本转化为数字，然后再进行处理。通常，对输入数据进行整理后，需要将其按照一定的规则进行编码，以便计算机能够更好地处理。

这一转换过程是通过词汇表进行的。词汇表是一个包含了所有可能出现的词的列表。对于一个给定的文本，可以按照该表格将文本转化为一个数字的序列。 而词表也需要根据文本的特点进行设计，以便更好地反映文本的特点。

题目描述

词汇表包括一系列的字符串，可以用于将输入的文本转换为数字序列。这里，我们认为输入文本事先经过一定的处理，将字母统一转换为了小写字母。词汇表的生成过程是一个迭代的过程。首先将文本按照一定的规则切分为单词序列， 并统计全部单词的出现频率。然后将单词拆分为单字母字符串，组成初始的词汇表。接下来根据词汇表中的词汇接连出现在单词中的频率，将词汇反复合并，组成更长的词汇加入到词汇表中。 词汇表的具体生成过程如下：

首先，输入文本中所有的单词和其出现的频率。然后，统计其中所有的字符，将其按照字典序排序，并将这些字符作为单字母字符串加入到词汇表中。同时，将输入的单词相应切分为词汇序列。

例如，输入下列词组和频率：

cut 15
cute 10
but 6
execute 3

则执行完上述过程后，词汇表中包含了 b、c、e、t、u、x 这些单字母字符串，而输入的词组被切分为：

c u t 15
c u t e 10
b u t 6
e x e c u t e 3

接下来，统计词汇表中，两个词汇组成的“词汇对”相连出现的频率，并选取出现次数最多的那一组拼接为一个字符串加入词汇表中。如果存在多个这样的“词汇对”，则再按照如下优先级顺序选取：

• 选取拼接后的字符串长度最短的那一组；
• 选取“词汇对”中前一个词汇长度最短的那一组；
• 选取拼接后的字符串字典序最小的那一组。

同时生成对应的合并规则（即将选出的“词汇对”合并成一个词汇），并按照该规则将所有输入单词的词汇序列按从前到后的顺序依次加以合并。

例如，在上述单词列表中词汇组合 <c, u> 在单词 cut 、 cute 和 execute 中分别出现了 15、10 和 3 次。相应统计全部的“词汇对”出现次数如下：

c u 28
u t 34
t e 13
b u 6
e x 3
x e 3
e c 3

于是，将 ut 加入词汇表中，并生成合并规则 <u, t>，可得到词汇表 b、c、e、t、u、x、ut。同时，将输入的单词切分为：

c ut 15
c ut e 10
b ut 6
e x e c ut e 3

上述过程可以重复进行。例如，继续统计“词汇对”出现的频率如下：

c ut 28
ut e 13
b ut 6
e x 3
x e 3
e c 3

这时，将 cut 加入词汇表中，并生成合并规则 <c, ut>，可得到词汇表 b、c、e、t、u、x、ut、cut。同时，将输入的单词切分为：

cut 15
cut e 10
b ut 6
e x e cut e 3

词汇表的生成，需要重复进行上述过程，直到词汇表达到指定的长度，或者所有输入的单词都被合并为一个词汇。

此外需要注意，一种特殊情况是选取的“词汇对”由两个相同的词汇组成。例如按“词汇对”<a, a> 进行合并时，由于从前到后的顺序要求，序列 a a a 会被合并为 aa a，而序列 a a a a 则会被合并为 aa aa。

输入格式

从标准输入读入数据。

输入的第一行包含两个正整数，$n$ 和 $m$，分别表示输入的单词的数量和期望的词汇表长度。

接下来的 $n$ 行，每行包含一个非空字符串 $s$ 和一个正整数 $f$，表示输入的单词和其出现的频率。其中，$s$ 中只包含小写字母。

输出格式

输出共 $m$ 行，每行包含一个字符串，按照加入词汇表的顺序输出词汇表中所有词汇。

4 8
cut 15
cute 10
but 6
execute 3

b
c
e
t
u
x
ut
cut

样例 1 解释

该样例即为题目描述中所举的例子。

子任务

对 $20\%$ 的数据，有 $n \leq 200$，$m$ 恰好等于输入单词中出现的所有字母的个数。

对 $40\%$ 的数据，有 $n \leq 200$，$m \leq 200$。

对 $80\%$ 的数据，有 $n \leq 2000$，$m \leq 2500$。

对 $100\%$ 的数据，有 $n \leq 10000$，$m \leq 5000$ 且大于等于输入单词中出现的所有字母的个数，输入单词的长度总和 $\sum |s|\le 2.5\times 10^5$，输入单词的总频率（$f$ 的总和）不超过 $10^6$。