시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

It is interesting if we can predict the weather for the future N days. Let A, B, . . . , Z stand for 26 different weather types. Denote the weather types of the future N days be W[1], . . . , W[N] where W[i] ∈ {A, B, . . . , Z}.

Assume that the meteorologists have a break-through result and they create a machine which can report a list of N − d + 1 weather patterns where each weather pattern is the weather types for d consecutive days. For example, assume N = 10 and d = 3. Suppose the sequence of N = 10 days of weather types is CRSCCCRSRR. (S, C, and R stand for sunny day, cloudy day, and rainy day, respectively.) Then, the machine will report N − d + 1 = 8 weather patterns in alphabetical order. For example, for the above weather sequence, the machine will output: CCC, CCR, CRS, CRS, RSC, RSR, SCC, and SRR. (Note that some weather patterns may occur more than once.)

In this task, for a fixed N and d, given the list of weather patterns generated by the machine, your aim is to compute a weather type for the first day and a weather type for the N-th day, such that both are consistent with the patterns reported by the machine. For the above example, you need to report C, R.

입력

Your program must read from the standard input N − d + 2 lines. The first line contains two integers N and d separated by spaces, where 3 ≤ N ≤ 1000 and 3 ≤ d ≤ 20. Each of the next N − d + 1 lines contains weather patterns.

출력

Your program must write two characters which represents the weather type of day 1 and day N to the standard output. There is no space in between the characters.

예제 입력 1

10 3
CCC
CCR
CRS
CRS
RSC
RSR
SCC
SRR

예제 출력 1

CR

힌트

We can formulate the problem as a graph problem. We create a graph G such that every weather pattern P[1] P[2] . . . P[d] corresponds to an edge between two nodes P[1] . . . P[d − 1] and P[2] . . . P[d]. The problem of reconstructing the weather sequence is equivalent to finding a path covering all edges in G.