《哈利波特》是小美最喜欢的一本小说。马上就是小美的生日了，作为生日礼物，蒜斜在网上下载了《哈利波特》1-7 部的英文文本，并按照顺序整理成了一本电子书。

然而，在整理完之后，蒜斜不小心运行了自己在《自然语言处理》课上写的洗数据代码，并将整理好的电子书文件覆盖了。具体来说：

1. 电子书文件中所有的大写字符都变成了小写字符。
2. 电子书文件中所有除了英文字母以外的符号，包括标点、空格、阿拉伯数字等，都被删除了。

现在，蒜斜辛辛苦苦整理好的电子书文件变成了一个包含小写字母的长度为 $4807976$ 的哈利波特串 $s$。

作为补救，他掏出了自己在《自然语言处理》课的大作业中用到的英文单词表 $D$（$D$ 中包含了 $370103$ 个英文单词），然后打算依此对哈利波特串 $s$ 进行分词。具体来说，他打算把 $s$ 切成若干段，并满足每一段要么是一个 $D$ 中出现过的单词，要么是一个单独的英文字母（即长度为 $1$ 的字符串）。不同的分词方案可能有很多，蒜斜定义一个分词方案的代价为这个方案将 $s$ 切成的段数，然后会从所以代价最小的方案中任选一个。

下面是一个简单的例子，假设字典中包含两个单词 suan 和 xie，那么 suan + x + i + e 和 suan + xie 都是字符串 suanxie 的分词方案。因为前者的代价为 $4$，后者的代价为 $2$，所以蒜斜会偏好于后者。

在字典的帮助下，蒜斜很轻松的将 $s$ 重新进行了分词，虽然分词的结果达不到完全通顺，但是好歹可以让人阅读了。

作为一名热爱动脑的 21 世纪大学生，蒜斜发现分词这个问题比他想象中的更加有趣，于是他就作了一下延伸的思考。

对于 $D$ 中的每一个单词 $w$，他定义 $w$ 的阿瓦达指数为哈利波特串 $s$ 所有没有用到单词 $w$ 的分词方案的最小代价。现在，蒜斜希望你帮她计算 $D$ 中阿瓦达指数最高的 $K$ 个单词，你能帮帮他吗。

输入格式

本题是一个提交答案题，本题的下发文件中包含如下部分：

1. harry-potter.txt 中存储了哈利波特串。
2. dict.txt 中按照字典序从小到大的顺序给出了 $D$ 中的所有单词。
3. harry1.in 和 harry2.in 是本题的两组测试数据，分别对应 Small Task 和 Large Task。

输入数据包含一行一个正整数 $K$，表示你需要找到的单词数量。

输出格式

你需要输出 $K$ 行，每行包含一个字符串和一个整数。其中第 $i$ 行的输出表示阿瓦达指数第 $i$ 高的单词和对应的阿瓦达指数。当存在两个单词的阿瓦达指数完全一样的时候，你需要优先输出字典序更小的那一个单词。

样例输出

这儿展示一个假象场景下的输出。假设需要分词的字符串是 suanxie，字典中仅包含两个单词 suan 和 xie，且 $K = 2$。这时对应的正确输出如下。

suan 5
xie 4

限制与约定

Small Task: $K = 2$

Large Task: $K = 200$。

下载

下发文件下载