H. Hoptimisation
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are practicing a sequence of hops on a rather boring hopscotch track consisting of several consecutive cells in a straight line, spaced 1m apart.

You have a planned route of cell names to visit. The total hopping distance depends on how you assign these names to the physical positions ($$$1$$$ to $$$k$$$).

For example, to complete the route A, B, A, C with the layout [A, B, C, D, E], the hops take $$$1 + 1 + 2 = 4$$$ metres total.

Illustration of Sample Input 1.

Given your sequence of hops, determine how to arrange the names across the cells (left to right) to minimize the total hopping distance.

Input
  • One line of input containing the number of cells, $$$k$$$ ($$$1 \le k \le 16$$$), and the number of hops, $$$n$$$ ($$$1 \le n \le 10^6$$$).
  • A second line of input containing $$$n$$$ lower-case strings, the $$$i\:$$$th string $$$s_i$$$ containing the target cell for the $$$i\:$$$th hop. ($$$1 \le |s| \le 10$$$).

It is guaranteed that no more than $$$k$$$ distinct cell names are given.

Output

Output $$$k$$$ strings of up to $$$10$$$ lower-case letters each: the names you want to assign to each cell from left to right. If there are multiple potential solutions, you may output any.

In case fewer than $$$k$$$ names are given in the input, feel free to invent more to fill the space.

Examples
Input
5 4
hop skip hop jump
Output
anything jump hop skip something
Input
9 16
a b c a b c a x y z x y z e f g
Output
g f e z y x a c b