namespace SAM
{
	struct qq{int son[26],pre,step;}s[N*2];int tot,Last;
	LL g[N];
	void Init ()	{tot=Last=1;memset(s,0,sizeof(s));memset(g,0,sizeof(g));}
	vector<int> vec[N];
	int r[N];
	void ins (int x)
	{
		int p=Last,np=++tot;
		s[np].step=s[p].step+1;r[np]=1;
		while (p!=0&&s[p].son[x]==0) s[p].son[x]=np,p=s[p].pre;
		if (p==0) s[np].pre=1;
		else
		{
			int q=s[p].son[x];
			if (s[q].step==s[p].step+1) s[np].pre=q;
			else
			{
				int nq=++tot;
				s[nq]=s[q];
				s[nq].step=s[p].step+1;
				s[np].pre=s[q].pre=nq;
				while (p!=0&&s[p].son[x]==q) s[p].son[x]=nq,p=s[p].pre;
			}
		}
		Last=np;
	}
	void dfs (int x)
	{
		if (g[x]!=0) return ;
		g[x]=r[x];
		for (int u=0;u<26;u++)
		{
			if (s[x].son[u]!=0) dfs(s[x].son[u]);
			g[x]+=g[s[x].son[u]];
		}
	}
	void get_r (int x)
	{
		int siz=vec[x].size();
		for (int u=0;u<siz;u++)
		{
			int y=vec[x][u];
			get_r(y);
			r[x]+=r[y];
		}
	}
	void get_g()
	{
		for (int u=2;u<=tot;u++) vec[s[u].pre].push_back(u);
		get_r(1);dfs(1);
	}
};