给定一个字符串集合 $S$，若由 $S$ 中 $k$ 个可相同的字符串拼接而成的字符串 $s$ 恰有 $k$ 个循环移位能由若干 $S$ 中的字符串拼成，则称其为好的。一个集合 $S$ 为好的，当且仅当所有能由 $S$ 中若干可相同的字符串拼接而成的字符串都是好的。给定字符串序列求有多少区间中的字符串集合是好的。

如果一个集合是好的，显然一个集合的所有子集都是好的，所以序列中的任意两个极长区间一定互不包含，可以双指针转化成做 $O(n)$ 次检查某个字符串集合 $S$ 是否是好的（注意这里需要去重）。

我们将“若干字符串拼接后得到两个互为循环移位的字符串 $s_1,s_2$”这个过程用一个图来表示：对集合 $S$ 中的每个字符串的每个非空后缀 $t$ 建两个状态分别表示 $s_1=s_2t$，和 $s_2=s_1t$；建空状态表示 $s_1=s_2$。

对字符串做 z-algorithm，可以 $O((\sum_{x\in S}|x|)^2)$ 地连边。途中有环则说明改集合不合法。

更进一步地，如果某个表示 $s_1=s_2t$ 的状态 $t$ 能够到达表示 $s_2=s_1t$ 的状态，根据对称性，它一定能到达它自己。所以对称的两个状态要么在同一个强连通分量里，要么互不能到达。据此我们可以给每个非空后缀只建一个点。

首先以 $m$ 条 special restrictions 为边建一幅无向图，对于某一分钟的选取方案，我们定义关键边为两侧的点一个被选中，另一个未被选中的边。

然后考察任意一条 $1\to n$ 的路径，不难发现，点 $1$ 总需要被选取，点 $n$ 不可以被选取，因此任何一种选取朋友的方案的任意一刻，这条路径上至少有一条关键边。而在一种游戏方案中，每一条边为关键边的时间不超过它的边权。于是游戏时长不可能超过 $1\to n$ 的任意一条路径的长度，也就不可能超过 $1\to n$ 的最短路。

证明了游戏时长存在一个上界，现在需要构造一种方案使得游戏时长能够达到这个上界。记 $d_i$ 为 $1\to i$ 的最短路，点 $i$ 在 $[1,d_i)$ 这个时间段不被选取，在 $[d_i,d_n]$ 的时间段被选取，于是任意一条边权为 $w$ 的边 $(u,v)$ 满足 $|d_u-d_v|\le w$（最短路的性质），而前者即这条边作为关键边的时长，从而保证了题目的 special restrictions 成立。

然后就可以如此构造答案。

对图的邻接矩阵应用矩阵乘法，限制路径上的边数做计数/最优化时，相当于每条边的边权为 $1$。但此时图具有边权，所以考虑把每条边拆成一条长为边权的链。这样点最多有 $(w-1)m+n$ 个，无法接受。于是我们考虑把从同一个点出发的边拆成的链进行合并。具体地，从每个点 $u$ 引出一条长为 $w$ 的链，然后从链上相应的节点连向 $u$ 的后继 $v$。

邻接矩阵做矩阵乘法需要记录边权，而此题需要对点权求最值。所以将每条边的边权定义为终点的点权，节点 $1$ 的点权单独统计。

美食节的处理看作点权修改，也即边权修改，快速幂过程中对于具有修改的时刻进行特殊处理即可。