Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register
ACM ICPC 2018 World Finals
Language:
Cellphones
 Time Limit: 6000MS Memory Limit: 65536K Total Submissions: 806 Accepted: 293

Description

The cows have started using cellphones to cowmunicate with each other, but have found that the button layout doesn't suit their hooves very well. They are designing a special cellphone with fewer but larger buttons.

One feature they liked on the standard cellphones was predictive text. Each button has a few letters associated with it, and one types a word by pushing the associated buttons. Because there is more than one letter for each button, this can be ambiguous for some words. However, most of the time the ambiguity can be resolved by using a dictionary to determine what word the user wanted.

Since the cows are designing a custom cellphone, they are also going to replace the English alphabet with the Cow alphabet. By an amazing coincidence, the cow alphabet is simply the first L (1 <= L <= 26) letters of the English alphabet, in the same order. They want to find out how to assign the letters of the Cow alphabet to the B buttons (1 <= B <= L) in such a way that the maximum number of words in their dictionary are unambiguous when entered with predictive text. Like normal cellphones, they want the letters on each button to be a contiguous section (one or more consecutive letters) of the alphabet.

Input

Line 1: Two space-separated integers: B and L

Line 2: D, the number of words in the dictionary (1 <= D <= 1000)

Lines 3..D+2: Each line contains one word from the dictionary in upper case and of length 1..10 characters. The words are presented in alphabetical order and with no duplicates.

Output

Line 1: The number of words in the Cow dictionary that have unique button sequences.

Lines 2..B+1: The nth line contains the letters that appear on button n, in upper case and alphabetical order. The lines must be listed in alphabetical order, and every Cow letter must appear exactly once. If there is more than one optimal solution, use the one that places the most letters on button 1. Ties are broken by placing the most letters on button 2, etc.

Sample Input

```3 13
11
ALL
BALL
BELL
CALK
CALL
CELL
DILL
FILL
FILM
ILL
MILK```

Sample Output

```7
AB
CDEFGHIJK
LM```

Hint

Explanation of the sample:

Button 1 contains AB, button two contains C-K, and button 3 contains LM. The words CELL, DILL, FILL and FILM are all entered as 2233, while the remaining 7 words are all entered uniquely.

Source

[Submit]   [Go Back]   [Status]   [Discuss]