Weather

Predicting the weather for the next $N$ days would be interesting. Let $A$, $B$, $\ldots$, $Z$ stand for 26 different weather types. Write the weather of the next $N$ days as $W[1], \ldots, W[N]$, where each $W[i]$ belongs to $\{A, B, \ldots, Z\}$.

Meteorologists made a breakthrough and built a machine that reports $N - d + 1$ weather patterns, where one weather pattern is the weather types of $d$ consecutive days. Suppose $N = 10$, $d = 3$, and the weather of the ten days is CRSCCCRSRR. Here S is a sunny day, C is a cloudy day, and R is a rainy day. The machine then reports $N - d + 1 = 8$ weather patterns in alphabetical order: CCC, CCR, CRS, CRS, RSC, RSR, SCC, SRR. The same weather pattern can appear more than once.

$N$ and $d$ are fixed, and you are given the list of weather patterns the machine produced. Compute the weather type of day 1 and the weather type of day $N$ so that both agree with the reported patterns. For the example above the answer is C and R.

The first line contains two integers $N$ and $d$ separated by a space ($3 \le N \le 1000$, $3 \le d \le 20$, $d \le N$).

Each of the next $N - d + 1$ lines contains one weather pattern, listed in alphabetical order. Every weather pattern is $d$ uppercase letters.

Print two characters, the weather type of day 1 and the weather type of day $N$, with no space between them.

Several answers can agree with the given list of weather patterns. In that case print the answer whose two characters, read as a string, come first in alphabetical order.

The problem can be restated as a graph problem. Build a graph $G$ in which every weather pattern $P[1] P[2] \ldots P[d]$ is an edge between the node $P[1] \ldots P[d-1]$ and the node $P[2] \ldots P[d]$. Reconstructing the weather sequence is the same as finding a path that covers every edge of $G$.