I saw it this morning kmp The idea of algorithm , Is not very good , I checked some more this afternoon kmp The template of , The specific steps are not very clear , But I made a question based on the template . Take a closer look at the details tomorrow .

Compress Words

Title Description

Amugae has a sentence consisting of nn words. He want to compress this sentence into one word. Amugae doesn't like repetitions, so when he merges two words into one word, he removes the longest prefix of the second word that coincides with a suffix of the first word. For example, he merges "sample" and "please" into "samplease".

Amugae will merge his sentence left to right (i.e. first merge the first two words, then merge the result with the third word and so on). Write a program that prints the compressed word after the merging process ends.

Input format

The first line contains an integer nn ( 1 \le n \le 10^51≤n≤105 ), the number of the words in Amugae's sentence.

The second line contains nn words separated by single space. Each words is non-empty and consists of uppercase and lowercase English letters and digits ('A', 'B', ..., 'Z', 'a', 'b', ..., 'z', '0', '1', ..., '9'). The total length of the words does not exceed 10^6106 .

Output format

In the only line output the compressed word after the merging process ends as described in the problem.

Title Translation

Amugae Yes n Word , He wants to put this n Words become a sentence , Specifically, it is to merge two words into one word from left to right . When merging two words , To find the biggest i(i\ge 0)i(i≥0), The length of the first word is ii The suffix of and the length of the second word are ii The prefix of is equal , Then put the second word ii The part after bit is connected to the first word . Output the last word

I/o sample

Input #1 Copy

5
I want to order pizza

Output #1 Copy

Iwantorderpizza

Input #2 Copy

5
sample please ease in out

Output #2 Copy

sampleaseinout

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int t[N];
char s[N],p[N];
int len1,len2;
void next(char p[])    // Find prefix table array t 
{
    int j,i;
    j=-1;
    t[0]=-1;
    i=0;
    while(i<len2-1)
    {
        if(j==-1||p[i]==p[j])
        {
            i++;
            j++;
            if(p[i]!=p[j]) t[i]=j;
            else t[i]=t[j];
        }
        else
            j=t[j];
    }
}
int kmp(char s[],char p[])
{
    int i,j;
    i=max(0,len1-len2);
    j=0;
    next(p);
    while(i<len1)
    {
        while(s[i]!=p[j])// When it doesn't match , Begin to think about next Array 
        {
            if(t[j]==0)// If there is no prefix in the substring , Substrings match from the beginning 
            {
                j=0;
                break;
            }
            else// The substring has the largest same prefix ,j from next[j] Start matching again at 
                j=t[j];
        }
        if(s[i]==p[j]) j++;
        i++;
    }
    return j;          // Go through the parent string to find the location of the child string 
}
int main()
{
    int n,i,j;
    cin>>n;
    cin>>s;
    n-=1;
    len1=strlen(s);
    while(n--)
    {
        cin>>p;
        len2=strlen(p);
        int c=kmp(s,p);
        i=len1-c;
        for(j=0;j<len2;j++)
        {
            s[i++]=p[j];      // Add the new string after the long string  
        }
        s[i]='\0';
        len1+=len2-c;
    }
    cout<<s;
    return 0;
}