Funny Language#526
There is a well-known word game: given a word, you must compose as many other words as possible from the letters of the original word. If a letter appears multiple times in the original word, you may use it up to that many times in the new words. The order of the letters does not matter. For example, given the word CONTEST, you can create the words NOTE, NET, ON, TEST, SET, etc.
Now you are tasked with creating a new dictionary. Your objective is to insert new words into it. You are given in advance words W_i (1 \leq i \leq m) which you will use in the game. You need to determine which new words should be added to the dictionary to maximize the total number of words you can compose using the letters from these words.
More formally, find a set of non-empty words such that |S| = n, and for every 1 \leq i \leq m, let S_i \subseteq S denote the subset of words from that can be made using the letters from W_i. Choose to maximize \sum_{i=1}^m |S_i|.
The first line contains two integers (1 \leq n \leq 100) — the number of new words you may add to the dictionary, and (1 \leq m \leq 1000) — the number of original words for the game.
Each of the following lines contains one of the original words. Each word consists of at most uppercase English letters (from A to Z).
Print lines, each containing one new word to be added to the dictionary.
Example 1