Today at the lesson Petya learned about non-suffix codes. A set of strings is called a non-suffix code if
- All rows in the set are distinct
- There is no pair of distinct strings such that one string is a suffix of the other
The string s is called the prefix of the string t if the length of the string s is not greater than the length of t, and also for any i, the i-th character of the string s matches the i-th character of the string t. For example, ab prefixes ab and abc, but does not prefix a and ac.
Petya decided to come up with something new and introduced a new concept — k-suffix code. This code he called a set of lines, such that:
- All rows in the set are distinct
- For any two distinct strings, the longest common prefix has length at most k
The greatest common prefix of two strings s and t is the longest string that is the prefix of both strings.
Now, given the set of strings s1, s2, ..., sn and the number k, Petya wants to find in this set a k-suffix-free code consisting of the maximum possible number of strings. Help him — find this code.
Input
The first line contains two numbers n and k — the number of rows in the set and the maximum length of the common prefix respectively (1 ≤ n ≤ 10
5, 1 ≤ k ≤ 100).
The i-th of the next n lines contains a string of lowercase Latin letters si — i-th word from the set (1 ≤ |si| ≤ 100).
It is guaranteed that the total length of all strings in the set does not exceed 10
6.
Imprint
On the first line print the number m - the maximum possible number of lines in the k-suffix-free code. In the i-th of the next m lines print the i-th element of this code. Code elements can be displayed in any order.
If there are multiple answers with maximum m, any one is allowed.
| Input |
Output |
5 2
cbaa
dbca
caa
abca
baa |
3
baa
caa
abca |
4 2
aa
cba
aa
bba |
3
aa
bba
cba |
Remark
In the first example, strings 1 and 5, as well as strings 2 and 4, have the largest common prefix greater than k, so the maximum number of strings that can consist of a k-prefix-free code is 3. In the second example, any pair of substrings has the largest common prefix no more than 2, however, since the code cannot contain the same lines, more than 3 lines cannot be included in it.