首先我们可以认为竹子不会重合。

我们令 $w\leftarrow w-n$，接下来只用考虑增加的长度。

然后，任意一个原串的周期均可以作为单次增加的长度。

使用 kmp 可以求出所有 Border，也即可以求出所有周期。

我们把最短周期单独提取出来，然后把剩下的部分的转移全部列出来，直接做一个同余最短路即可。

直接做 dijkstra 是 $O(n^2\log n)$ 或者 $O(n^2)$ 的，看上去不优。考虑能不能优化一下。

由 Border 理论，原串的所有周期构成 $O(\log n)$ 个等差数列。考虑不使用 dijkstra，而是每次逐步插入一个等差数列的贡献；由于同余最短路的特性，我们可以认为是在图上依次走过各类边，显然答案不会改变。

假设最短周期长度为 $g$，要通过某一个等差数列 $l+dx,x\in[0,k)$ 更新外界。

考虑把 $x,(x+d)\bmod g,(x+2d)\bmod g,\dots,(x-d)\bmod g$ 放进一个等价类，那么每个转移都是用一个等价类中的元素更新另一个等价类中的一段连续元素；也可能是对等价类内部进行更新。

假设我们按当前距离从小到大排序并插入堆中，更新一段元素时，我们注意到每个元素最多被更新一次，因此如果某个还没被更新的元素的下一项是一个已经被更新过了的元素，我们可以直接退出更新的过程。

使用并查集之类的东西容易快速找到某个位置之后第一个未被更新的位置。

直接这样做的复杂度是 $O(n\log^2n)$ 的，仍然很难过得去。

考虑能不能做的更好。

注意到我们现在是钦定了一个 $g$ 的，我们考虑每次更换一个 $g$，使得当前 $g$ 等于当前 $l$，则此时只有等价类内部的更新，从而可以直接使用单调队列来求最短路。

考虑怎么支持换模数。

我们要从 $g$ 变成 $l$，那么假设初始数组为 $d_{0\sim g-1}$，最终数组为 $D_{0\sim l-1}$，我们有更新方向

这就相当于是 $D_{d_k\bmod l}\leftarrow d_k$ 之后再加了 $g$ 的边。直接同样划分等价类然后扫两圈即可。

代码常数太大，无法直接通过 uoj hack 数据，就不贴了。