题目描述

有 $n$ 段口令需要按给定顺序拼成一段总口令。为了避免相邻位置出现重复片段，每次把当前总口令与下一段口令合并时，可以删除下一段口令开头的一段字符。

具体地，设当前总口令为 $s$，下一段口令为 $t$。你需要找到一个最长字符串，使它既是 $s$ 的后缀，又是 $t$ 的前缀，然后只把 $t$ 中剩余的后半部分接到 $s$ 后面。

按照从左到右的顺序依次合并所有口令，输出最后得到的总口令。

输入格式

第一行输入一个整数 $n$，表示口令段数。

第二行输入 $n$ 个由单个空格分隔的非空字符串，表示这些口令段。

输出格式

输出一行一个字符串，表示全部合并后的总口令。

样例

6
ababa bac acd d0 D0abc abcXYZ

ababacd0D0abcXYZ

样例说明

合并时会区分大小写，因此 $d0$ 与 $D0abc$ 之间不会产生长度为 $2$ 的重合。

数据范围

• 对于 $30\%$ 的数据，所有字符串的总长度不超过 $1000$。
• 对于 $100\%$ 的数据，$1\le n\le 10^5$，每个字符串仅包含大写字母、小写字母和数字，且所有字符串的总长度不超过 $10^6$。