/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 625 点
問題文
N 個の文字列 S_1,\ldots,S_N が与えられます。
全ての要素が 1 以上 N 以下であるような長さ K の数列 (A_1,\ldots,A_K) に対し、
文字列 f(A_1,\ldots,A_K) を S_{A_1}+S_{A_2}+\dots+S_{A_K} と定めます。ここで + は文字列の連結を表します。
N^K 個の数列全てについての f(A_1,\dots,A_K) のうち辞書順最小の文字列を求めてください。
制約
- 1\leq N \leq 10^5
- 1\leq K \leq 10^5
- S_i は英小文字からなる長さ 10 以下の文字列
- N,K は整数
入力
入力は以下の形式で標準入力から与えられる。
N K S_1 \vdots S_N
出力
答えを出力せよ。
入力例 1
3 2 abc xxx abc
出力例 1
abcabc
- f(1,1)=
abcabc - f(1,2)=
abcxxx - f(1,3)=
abcabc - f(2,1)=
xxxabc - f(2,2)=
xxxxxx - f(2,3)=
xxxabc - f(3,1)=
abcabc - f(3,2)=
abcxxx - f(3,3)=
abcabc
であり、これらのうち辞書順最小は abcabc です。
入力例 2
4 3 abcd abc ab a
出力例 2
aaa
入力例 3
3 2 cba cb c
出力例 3
cbac
Score : 625 points
Problem Statement
You are given N strings S_1,\ldots,S_N.
For a sequence (A_1,\ldots,A_K) of length K where all elements are between 1 and N, inclusive,
define the string f(A_1,\ldots,A_K) as S_{A_1}+S_{A_2}+\dots+S_{A_K}. Here, + represents string concatenation.
Among all f(A_1,\dots,A_K) for the N^K sequences, find the lexicographically smallest string.
Constraints
- 1\leq N \leq 10^5
- 1\leq K \leq 10^5
- S_i is a string consisting of lowercase English letters with length at most 10.
- N and K are integers.
Input
The input is given from Standard Input in the following format:
N K S_1 \vdots S_N
Output
Output the answer.
Sample Input 1
3 2 abc xxx abc
Sample Output 1
abcabc
- f(1,1)=
abcabc - f(1,2)=
abcxxx - f(1,3)=
abcabc - f(2,1)=
xxxabc - f(2,2)=
xxxxxx - f(2,3)=
xxxabc - f(3,1)=
abcabc - f(3,2)=
abcxxx - f(3,3)=
abcabc
Among these, the lexicographically smallest is abcabc.
Sample Input 2
4 3 abcd abc ab a
Sample Output 2
aaa
Sample Input 3
3 2 cba cb c
Sample Output 3
cbac