날씨

앞으로 $N$일 동안의 날씨를 미리 알 수 있다면 흥미로울 것이다. $A$, $B$, $\ldots$, $Z$는 서로 다른 26가지 날씨 종류를 나타낸다. 앞으로 $N$일의 날씨를 $W[1], \ldots, W[N]$이라고 하고, 각 $W[i]$는 $\{A, B, \ldots, Z\}$의 원소이다.

기상학자가 획기적인 연구 성과를 내서, 연속한 $d$일의 날씨 종류로 이루어진 날씨 패턴 $N - d + 1$개를 알려주는 기계를 만들었다. 예를 들어 $N = 10$, $d = 3$이고 열흘 동안의 날씨가 CRSCCCRSRR이라고 하자. S는 맑음, C는 흐림, R은 비를 뜻한다. 이때 기계는 날씨 패턴 $N - d + 1 = 8$개를 사전순으로 CCC, CCR, CRS, CRS, RSC, RSR, SCC, SRR과 같이 알려준다. 같은 날씨 패턴이 두 번 이상 나올 수도 있다.

$N$과 $d$가 고정되어 있고, 기계가 만든 날씨 패턴 목록이 주어진다. 이 목록과 모순이 없는 첫째 날의 날씨와 $N$째 날의 날씨를 구하는 프로그램을 작성하시오. 위 예시라면 C와 R을 답해야 한다.

첫째 줄에 $N$과 $d$가 공백으로 구분되어 주어진다. ($3 \le N \le 1000$, $3 \le d \le 20$, $d \le N$)

다음 $N - d + 1$개 줄에 날씨 패턴이 사전순으로 한 줄에 하나씩 주어진다. 날씨 패턴은 모두 알파벳 대문자 $d$개로 이루어진다.

첫째 날의 날씨와 $N$째 날의 날씨를 나타내는 문자 두 개를 공백 없이 출력한다.

주어진 날씨 패턴 목록과 모순이 없는 답이 여러 개일 때가 있다. 그런 경우에는 두 문자를 이어 붙인 문자열이 사전순으로 가장 앞서는 답을 출력한다.

이 문제는 그래프 문제로 바꿔 풀 수 있다. 날씨 패턴 $P[1] P[2] \ldots P[d]$마다 정점 $P[1] \ldots P[d-1]$과 정점 $P[2] \ldots P[d]$를 잇는 간선을 만들어 그래프 $G$를 얻는다. 날씨 순서를 복원하는 문제는 $G$의 모든 간선을 지나는 경로를 찾는 문제와 같다.