# LA 5794

Solução: Lucas Castro

#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <cstring>
#include <set>

using namespace std;

typedef long long int ll;

#define MAXN 70
#define MAXC 10010
#define INF 0x3f3f3f3f
#define N MAXN*MAXC

int n;
int sz[MAXN];
ll who[MAXN*MAXC];

char str[N], inp[N];
int H, Bucket[N], nBucket[N], Rank[N], Height[N], c;

typedef pair<int,ll> ill;

struct Suffix {
int idx; // Suffix starts at idx, i.e. it's str[ idx .. L-1 ]
bool operator<(const Suffix& sfx) const
// Compares two suffixes based on their first 2H symbols,
// assuming we know the result for H symbols.
{
if(H == 0) return str[idx] < str[sfx.idx];
else if(Bucket[idx] == Bucket[sfx.idx])
return (Bucket[idx+H] < Bucket[sfx.idx+H]);
else
return (Bucket[idx] < Bucket[sfx.idx]);
}
bool operator==(const Suffix& sfx) const {
return !(*this < sfx) && !(sfx < *this);
}
} Pos[N];

int UpdateBuckets(int L) {
int start = 0, id = 0, c = 0;
for(int i = 0; i < L; i++) {
if(i != 0 && !(Pos[i] == Pos[i-1])) {
start = i;
id++;
}
if(i != start)
c = 1;
nBucket[Pos[i].idx] = id;
}
memcpy(Bucket, nBucket, 4 * L);
return c;
}

void SuffixSort(int L) {
H = 0;
for(int i = 0; i < L; i++) Pos[i].idx = i;
sort(Pos, Pos + L);
c = UpdateBuckets(L);
for(H=1;c;H *= 2) {
// Sort based on first 2*H symbols, assuming
// that we have sorted based on first H character
sort(Pos, Pos+L);
// Update Buckets based on first 2*H symbols
c = UpdateBuckets(L);
}
}

// Must compute the suffix array Pos first
void ComputeLCP(int L) {
for (int i = 0; i < L; i++) Rank[Pos[i].idx] = i;
int h = 0;
for (int i = 0; i < L; i++)
if (Rank[i] > 0) {
int k = Pos[Rank[i] - 1].idx;
while (str[i+h] == str[k+h])
++h;
Height[Rank[i]] = h;
if (h > 0) --h;
}
}

set<ll> s;
string saux;
set<string> ss;
int len[N];

int main(){
int m;
int t = 49;
while(scanf(" %d",&m) == 1 && m > 0){
n = 0;
for(int i = 0 ; i < m ;i++){
cin >> saux;
for(int j = 0 ; j < saux.size() ; j++){
str[n++] = saux[j];
}
str[n++] = 'a' - 1 - i;
}
str[n++] = '\0';

int last = INF;
int k = m;
for(int i = n - 2 ; i >= 0 ; i--){
if(str[i] < 'a'){
k--;
last = i;
continue;
}else{
who[i] = k;
len[i] = last - i;
}
}

SuffixSort(n);
ComputeLCP(n);

/* Pos[i].idx guarda a posicao na string original */
s.clear();

for(int i = 0 ; i < n - 1 ; i++) Height[i] = Height[i+1];
Height[n-1] = 0;

vector<ill> pilha;

for(int i = m + 1 ; i < n; i++){
if(Height[i] < len[Pos[i].idx] && (i == m + 1 || Height[i-1] < len[Pos[i].idx])){
s.insert(1LL << who[Pos[i].idx]);
}
ll mask = 0LL;

while(!pilha.empty() && Height[i] < pilha.back().first){
pilha.pop_back();
}
if(!pilha.empty()) pilha.back().second |= mask;

if(Height[i] == 0)  continue;

if(pilha.empty() || Height[i] > pilha.back().first){
mask |= (1LL << who[Pos[i].idx]) | (1LL << who[Pos[i + 1].idx]);