无论怎样神树大人都会删库跑路()

首先看到这个 \(Q\) \(1e9\) 的范围和 \(R_i\) 下标的取模操作，便知道这个东西有循环节，因此稍微思考一下便可以求出循环节，但注意，字符串的首尾两个特殊位置是不在循环内的，需要特殊处理。

然后就处理掉了 \(Q\)，考虑线性求解。

容易发现，需要求的是不断在一个队列中加入字符串，并判断它的后缀重排后是否与另一个字符串 \(S\) 相等。暴力判断是平方的，但判断两个字符串是否相等，不难想到 \(hash\)。

考虑对每一个数随机映射一个值乱搞，因为这里是重排后相等，因此不能使用多项式 \(hash\)，即字符间没有相对顺序。

然后用双端队列维护一下就做完了。

————————

首先看到这个 \(Q\) \(1e9\) 的范围和 \(R_i\) 下标的取模操作，便知道这个东西有循环节，因此稍微思考一下便可以求出循环节，但注意，字符串的首尾两个特殊位置是不在循环内的，需要特殊处理。

然后就处理掉了 \(Q\)，考虑线性求解。

容易发现，需要求的是不断在一个队列中加入字符串，并判断它的后缀重排后是否与另一个字符串 \(S\) 相等。暴力判断是平方的，但判断两个字符串是否相等，不难想到 \(hash\)。

考虑对每一个数随机映射一个值乱搞，因为这里是重排后相等，因此不能使用多项式 \(hash\)，即字符间没有相对顺序。

然后用双端队列维护一下就做完了。