Universal Cup Judging System

Universal Cup

시간 제한: 2.0 s 메모리 제한: 1024 MB 총점: 100 해킹 가능 ✓
통계

畀定 $N$ 個字串 $S_1, \dots, S_N$,每個字串都由細楷英文字母組成,而且長度都係 $M$。

一開始,設 $X = S_1$,然後執行以下操作 $N - 1$ 次。

喺第 $i$ 次操作入面,設 $Y$ 為將 $X$ 同 $S_{i+1}$ 按呢個順序拼接而成嘅字串。然後,揀選 $Y$ 嘅任意一個長度為 $M$ 嘅連續子字串,並將 $X$ 替換為嗰個子字串。

請輸出 $X$ 最終可能得到嘅字典序最細嘅字串。

Input

第一行按順序包含整數 $N, M$。($2 \le N \le 2000, 1 \le M \le 2000$)

接住落嚟嘅 $N$ 行,每行包含一個長度為 $M$、由細楷英文字母組成嘅字串 $S_i$。

Output

印出答案。

Examples

Input 1

2 3
cat
cut

Output 1

atc

Input 2

2 1
a
b

Output 2

a

Input 3

3 8
jastaway
tatesoto
soryuusi

Output 3

asoryuus

Note

喺第一個範例入面,一開始 $X = \texttt{cat}$。 喺第一次操作入面,$Y = \texttt{catcut}$。如果我哋揀由第 $2$ 個字元到第 $4$ 個字元嘅連續子字串,咁 $X = \texttt{atc}$,呢個就係可能嘅字典序最細結果。

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#1629EditorialOpenO(n^3 log \sum /w) 做法tzl_Dedicatus545View
#1523EditorialOpen题解jianglyView
#1506EditorialOpenO(n^3) 做法incentView

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.