Amugae 有一个由 $$$n$$$ 个单词组成的句子。他想把这句话压缩成一个词。 Amugae 不喜欢重复,因此当他将两个单词合并为一个单词时,他会删除第二个单词中与第一个单词的后缀重合的最长前缀。例如,他将“sample”和“please”合并为“samplease”。
Amugae 将从左到右合并他的句子(即首先合并前两个单词,然后将结果与第三个单词合并,依此类推)。编写一个程序,在合并过程结束后打印压缩后的字。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$),即 Amugae 句子中的单词数。
第二行包含 $$$n$$$ 个单词,以单个空格分隔。每个单词非空,由大小写英文字母和数字组成('A'、'B'、...、'Z'、'a'、'b'、...、'z'、'0'、'1'、...、'9')。单词总长度不超过$$$10^6$$$。
输出
在合并过程结束后,在唯一的行中输出压缩字,如问题中所述。
示例
输入 #1
5 I want to order pizza
输出 #1
Iwantorderpizza
输入 #2
5 sample please ease in out
输出 #2
sampleaseinout