WORD - Wordplay

Ivana made up a long word of N letters. Then she wrote down all K-letter-substrings of that word. For example, if the original word is BANANA and K=3, Ivana writes down the words BAN, ANA, NAN, ANA. The number of these words is, obviously, N-K+1.

Ivana sorted these words in lexicographic order (in the given example, that would be ANA, ANA, BAN, NAN).

But the sad thing happened: Ivana forgot the original word! Your task is to reconstruct it. A unique solution will exist in all of the test data.

Constraints: 3 ≤ N ≤ 100 000, 2 ≤ K ≤ 15, K < N.

Input

[integers N, K]

[N-K+1 words in lexicographic order, each consisting of capital English letters]

Output

[the required word]

Example

Input:
6 3
ANA
ANA
BAN
NAN

Output:
BANANA

Added by:Adrian Satja Kurdija
Date:2011-04-19
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own problem

hide comments
2013-09-18 21:50:40 Flyers
best problem ever....
finally solved!!!!!!!!!!

@Ravi Kiran really it tested all my concepts
2011-09-14 09:34:08 Ravi Kiran
Really Like the Problem. Tested lots of things in my opinion.
@Adrian: Thanks.

Last edit: 2011-04-22 09:05:39
2011-09-14 09:34:08 abhijith reddy d
Cool Problem.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.