## Problem H. Hot-keys ≡

 Author: A. Klenin Time limit: 5 sec Input file: input.txt Memory limit: 64 Mb Output file: output.txt

### Statement

When designing dialog forms for interactive programs, it is important to assign hot-keys (known also as accelerator keys) to each dialog element, so as to facilitate keyboard input.

For better mnemonics, hot-keys are assigned based on the letters of dialog elements' captions, usually favoring letters near the beginning of caption. Manual hot-keys distribution can be tedious and error-prone, as one must be careful not to assign same letter to different elements.

Your program will be given a list of captions. It must assign unique hot-keys to as many captions of possible. Each assigned hot-key must be a letter from the corresponding caption.

For each hot-key, position is the leftmost occurrence of the hot-key letter in the corresponding caption. From all solutions with the same numbers of hot-keys, your program must choose the one with minimal sum of hot-key positions. If there is still more than one optimal solution, output any of them.

### Input file format

Input file contains number of captions N followed by N lines with captions.

### Output file format

Output file must contain N lines with the same captions as in input. In those captions which have hot-key assigned, leftmost occurrence of hot-key letter must be preceded with '&' (ASCII 38).

### Constraints

1 ≤ N ≤ 10, all captions are from 1 to 10 characters in length and consist of small Latin letters.

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3
yes
no
cancel
&yes
&no
&cancel
2
4
abc
bca
acb
aaaa
&amp;abc
&amp;bca
a&amp;cb
aaaa

0.035s 0.007s 15