某人读论文，一篇论文是由许多单词组成。但他发现一个单词会在论文中出现很多次，现在想知道每个单词分别在论文中出现多少次。

第一个一个整数N,表示有多少个单词，接下来N行每行一个单词。每个单词由小写字母组成，N<=200,单词长度不超过10^6

输出N个整数，第i行的数字表示第i个单词在文章中出现了多少次。

/*  AC自动机模板*/#include<iostream>#include<cstdio>#include<cstring>#define N 1000007using namespace std;int sz,n;char s[N];int son[N][26],fail[N],q[N],sum[N],loc[N];inline void clear(){    sz=1;    for(int i=0;i<26;i++) son[0][i]=1;}void insert(int &pos){    int x=1,l=strlen(s);    for(int i=0;i<l;i++)    {        if(!son[x][s[i]-‘a‘]) son[x][s[i]-‘a‘]=++sz;        x=son[x][s[i]-‘a‘];sum[x]++;//以x为结尾的单词数加一     }    pos=x;}void buildfail(){    int head=0,tail=1;q[0]=1;fail[1]=0;    while(head<tail)    {        int now=q[head++];        for(int i=0;i<26;i++)//更新fail指针         {            if(!son[now][i]) continue;            int ff=fail[now];            while(!son[ff][i]) ff=fail[ff];            fail[son[now][i]]=son[ff][i];            q[tail++]=son[now][i];        }    }    for(int i=tail-1;i>=0;i--) sum[fail[q[i]]]+=sum[q[i]];//因为以fail[q[i]]结尾的单词一定在以q[i]结尾的单词中出现 }int main(){    clear(); scanf("%d",&n);    for(int i=1;i<=n;i++) scanf("%s",s),insert(loc[i]);    buildfail();    for(int i=1;i<=n;i++) printf("%d\n",sum[loc[i]]);    return 0;}