Home Web Board ProblemSet Standing Status Statistics
long long输出请使用 %lld服务器的python版本为3.4
Problem B: 背单词

Problem B: 背单词

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 223  Solved: 37
[Submit][Status][Web Board]

Description

    Lint最近背起了单词。要背的单词实在太多了,Lint根本背不过来。于是,Lint发明了一种新的背单词的方法。

    对于两个单词S1, S2, Lint会自己创造一个新的单词S, S同时包含了S1S2(即S有某个连续的一段和S1相等,也有某个连续的一段和S2相等,这两段在S中可以有公共部分)。Lint认为只要背掉了S, 就相当于背掉了S1, S2,这样就可以减少要背的单词的数量了。为了让自己能够背得更轻松,Lint希望S的长度尽量短,如果存在多个长度相等的S, Lint会选择字典序最小的那一个。

Input

多组数据读入。

每组数据第两行是两个正整数n, m1 <= n, m <= 1000),分别表示S1S2的长度。

接下来两行分别描述S1, S2

S1S2只由小写字母组成,并且一定不相等。

Output

对于每组数据,输出最优的S

Sample Input

6 7
layout
display
4 6
rain
number

Sample Output

displayout
numberain

HINT

[Submit][Status][Web Board]