LG5028

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=1e6+57;

int s[N];
int SA[N];
int Rank[N];
int tmp[N];
int cnt[N];

inline void GetSA(int n){
    int m=s[n];
    for(int i=1;i<=n;++i)Rank[i]=s[i];
    for(int i=1;i<=n;++i)cnt[Rank[i]]++;
    for(int i=1;i<=m;++i)cnt[i]+=cnt[i-1];
    for(int i=n;i>=1;--i)SA[cnt[Rank[i]]--]=i;
    for(int l=1,p=0;p<n;l<<=1){
        p=0;
        for(int i=1;i<=l;++i)tmp[++p]=n-i+1;
        for(int i=1;i<=n;++i)if(SA[i]>l)tmp[++p]=SA[i]-l;
        for(int i=1;i<=m;++i)cnt[i]=0;
        for(int i=1;i<=n;++i)cnt[Rank[i]]++;
        for(int i=1;i<=m;++i)cnt[i]+=cnt[i-1];
        for(int i=n;i>=1;--i)SA[cnt[Rank[tmp[i]]]--]=tmp[i];
        swap(tmp,Rank);
        Rank[SA[1]]=p=1;
        for(int i=2;i<=n;++i){
            if(tmp[SA[i]]!=tmp[SA[i-1]]||tmp[SA[i]+l]!=tmp[SA[i-1]+l])p++;
            Rank[SA[i]]=p;
        }
        m=p;
    }
}

int Hight[N];

inline void GetHight(int n){
    for(int i=1,p=0;i<=n;++i){
        if(Rank[i]==1)continue;
        int j=SA[Rank[i]-1];
        if(p)--p;
        while(s[i+p]==s[j+p])p++;
        Hight[Rank[i]]=p;
    }
}

char str[N];
int ID[N];
int Min[55];
int Ans[55][55];

int main(){
    int n,p=0;r(n);
    for(int i=1;i<=n;++i){
        scanf("%s",str);
        int len=strlen(str);
        for(int j=0;j<len;++j){
            s[++p]=str[j]-'a'+1;
            ID[p]=i;
        }
        s[++p]=26+i;
    }
    GetSA(p);
    GetHight(p);
    for(int i=1;i<=p;++i){
        int x=SA[i];
        for(int j=1;j<=n;++j){
            Min[j]=min(Min[j],Hight[i]);
            Ans[ID[x]][j]=max(Ans[ID[x]][j],Min[j]);
        }
        if(ID[x])Min[ID[x]]=1e9;
    }
    for(int i=1;i<=n;++i,puts("")){
        for(int j=1;j<=n;++j){
            if(i!=j)printf("%d ",max(Ans[i][j],Ans[j][i]));
        }
    }
}