题目描述

给定 $N$ 个互不相同的单词，所有单词都只由小写英文字母 a 到 z 组成。

你站在一个命令行终端前，需要输入若干单词。当前终端中有一个字符串，一开始为空。你可以执行两种操作：

1. 在当前字符串末尾添加一个字符；
2. 删除当前字符串的最后一个字符，只有当当前字符串非空时才能执行。

如果在某一时刻，终端中的当前字符串恰好等于某个单词，则认为这个单词已经被输入过。

给定一个正整数 $K$。对于每个 $i=1,2,\ldots,K$，你需要从这 $N$ 个单词中选择 $i$ 个互不相同的单词，使得输入这 $i$ 个单词所需的操作次数最少。

注意：对于每个 $i$，终端中的字符串都从空串开始，并且最终也必须回到空串。

输入格式

第一行包含两个整数 $N,K$。

接下来 $N$ 行，每行包含一个单词。

输出格式

输出 $K$ 行。

第 $i$ 行输出一个整数，表示选择并输入 $i$ 个不同单词所需的最少操作次数。

数据范围与约定

• $1\le K\le N$；
• 所有单词长度之和不超过 $1\,000\,000$；
• 所有单词互不相同，只包含小写英文字母。

子任务

样例

输入

3 3
a
b
absc

输出

2
4
10

解释

对于 $i=1$，选择单词 a，操作过程为：

空串 -> a -> 空串

共需要 $2$ 次操作。

对于 $i=2$，可以选择单词 a 和 b，共需要 $4$ 次操作。

对于 $i=3$，必须输入全部三个单词，最少需要 $10$ 次操作。