LCS2

#include <bits/stdc++.h>
#define MAX 100000

using namespace std;

string txt, palavra;
queue<string> q;
struct node{
    int future[27];
    int past, len;
} sa[2*MAX];

int sz, last;

void init(){
    sz = 1;
    last = 0;
    sa[0].past = -1;
    sa[0].len = 0;
}

void extends(int c){
    int cur = sz++;
    sa[cur].len = sa[last].len + 1;

    for(; last != -1 && !sa[last].future[c]; last = sa[last].past) sa[last].future[c] = cur;

    if(last == -1) sa[cur].past = 0;
    else{
        int q = sa[last].future[c];
        if(sa[q].len == sa[last].len + 1) sa[cur].past = q;
        else{
            int clone = sz++;
            sa[clone].len = sa[last].len + 1;
            sa[clone].past = sa[q].past;
            memcpy(sa[clone].future, sa[q].future, sizeof sa[q].future);
            for(; last != -1 && !sa[last].future[c] ==  q; last = sa[last].past) sa[last].future[c] = clone;
            sa[cur].past = sa[q].past = clone;
        }
    }
    last = cur;
}

void clear(int size){
    for(int i = 0; i < palavra.size(); i++) {
        memset(sa[i].future, 0, sizeof sa[i].future);
        sa[i].past = 0;
        sa[i].len = 0;
    }
    init();
}
void lcs(){
    string nova = "";
    while(q.size() > 1){
        txt = q.front();
        q.pop();
        palavra = q.front();
        q.pop();
        clear(palavra.size());

        for(int i = 0; i < txt.size(); i++) extends(txt[i]-'a');
        int l = 0, best = 0, v = 0;
        nova = "";
        for(int i = 0; i < palavra.size(); i++){
            bool flag = false;
            while(v && !sa[v].future[palavra[i]-'a']){
                v = sa[v].past;
                l = sa[v].len;
                if(!flag){
                    nova += "{";
                    flag = true;
                }
            }


            if(sa[v].future[palavra[i]-'a']){
                nova += palavra[i];
                //cout << palavra[i] << endl;
                v = sa[v].future[palavra[i]-'a'];
                l++;
            }else {
                if(nova[nova.size()-1] != '{') {
                    nova += "{";
                    //cout <<'{' << endl;
                }
            }

        }
        q.push(nova);
        cout << nova << endl;
    }
    cout << endl;
    cout << nova << endl;
}
int main(){
    int num; cin >> num;
    while(num--){
        cin >> txt;
        q.push(txt);
    }
    cout << endl;
    lcs();
    return 0;
}