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

Input

多组数据读入。

每组数据第两行是两个正整数n, m（1 <= n, m <= 1000），分别表示S1和S2的长度。

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

S1和S2只由小写字母组成，并且一定不相等。

Output

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

Sample Input

6 7
layout
display
4 6
rain
number

Sample Output

displayout
numberain

HINT

[Submit][Status][Web Board]