//T1:给你n个点,其中m个没有入度,接受.
//没有出度为终点.问,每个终点最终的水量.
//先考虑直接模拟.
//找出m(m很小)个起点,然后,dfs.
//Beware of your long long
//过完dyl了,记得最后15min检查long long
//
//T2:数据范围大概1e5+5e4的样子。
//先考虑一个暴力。
//C是一定在最后的，我们考虑从后往前枚举C。
//然后看前面的循环的个数，设前面的循环节为SS。
//那么就有(|S|-|C|)/(|SS|)个基循环节。
//里面随便划分两个字符串分别做A,B，方案数为|S|-1。
//然后我们可以用基循环节再组成一些新的循环节，这个要看(|S|-|C|)/(|SS|)的因数个数。
//但是我们需要满足F(A)<=F(C)。
//这个我们每次统计一遍即可。
//但是但是
//如何找循环节？
//找出来了。
//然后，我们把循环节中所有前缀（不含空串）的F值找出来，计为funa[j],1<=j<i。
//然后把(|S|-|C|)/(|SS|)的因数分解出来，计为ps[k]，然后就计算funa[j]*ps[k]<=F(C)的情况有多少种，但是时间复杂度好像退化le，好像没有，。算了先打。
//哦对了我们可以把funa排个序，用单调性来优化成O(n^2*log)应该能过一半左右。（funa本身不具有单调性。）
//
//思路比较乱，重新整理一下如何计算答案。
//设当前的C=S[i,n]。
//枚举的前缀A=S[1,j]，B=S[j+1,i-1]（不关心）
//设M=(|S|-|C|)/(|SS|)，即基循环节=SS一共有多少节。
//设P(M)表示M的某一个因数。
//如果当前的F(A)<=F(C)，那么对于P(M)为奇数的情况，我们用P(M)个SS可以重新组成又一个循环节。
//枚举一个j in [1,i-2]，来计算答案。
//这里相当于把我们当前的S[1,i-1]分成了M段，看当前我们枚举的j在哪一段。
//设在第x段，如果x|M，那么ans+=M/x；否则ans++。
//计算当前在哪一段：
//法1：用变量
//法2：算
//恩，dyl没过。初步判断是算漏了，不存在算重的问题。
//不好像也有算多了。。。1
//大概知道哪里有问题了。
//当|SS|=1时，一个循环节里不知道怎么摆B。
//需要特判，当|SS|=1，不算基循环节的贡献。
//不过我答案是少了阿。。。
//还是不行。
//
//
//3
//nnrnnr
//zzzaab
//mmlmmlo

		lps[len] = mps[1];
		// how to work the "loop day (xun huan jie)" out
		// open an array to store the LD
		// then (for j=2 to i-1), t	o "beautiful orange (mei ju)" the prefix
		// cur means currently we where we should match (under S LD meaning)
		// len means the length of the LD
		// lst means the previous fail matched position
		// when we "lost match (shi pei)" we then add S[lst,j] into the LD
		// then put lst into zero,put cur into one
		// when finish 1 round matching (cur==len+1), we should:
		// 1. change cur into 1
		// 2. change lst into j+1
		// remember to special check if the (|S|-|C|)/(|SS|) isn't in Z situation
		for ( int j = 2; j < i; ++ j ) {
			if ( mps[j] != lps[cur] ) {
				cur = 1;
				for ( int k = lst; k <= j; ++ k )	lps[++ len] = mps[k];
				lst = j + 1;
			}
			else {
				cur ++;
				if ( cur == len + 1 )	cur = 1;
			}
//			oneDebug ( j, cur, lst, len );
		}
		if ( ( i - 1 ) % len ) {
			len = i - 1;
			for ( int j = 1; j <= len; ++ j )	lps[j] = mps[j];
		}