CF484C Strange Sorting

你知道多少种特定的排序方式？升序、降序、按长度升序、按极角升序……现在让我们了解另一种特定的排序方式：$d$-排序。$d$-排序适用于长度至少为 $d$ 的字符串，其中 $d$ 是某个正整数。字符串中的字符将按照如下方式排序：首先放所有初始字符串下标为 $0$ 的字符，然后是所有下标为 $1$ 的字符，然后是所有下标为 $2$ 的字符，依此类推，最后是所有下标为 $d-1$ 的字符。这里所说的第 $i$ 个字符，指的是所有位置对 $d$ 取模余数等于 $i$ 的字符。如果两个字符所在位置对 $d$ 取模后的余数相同，那么它们在排序后的相对顺序应保持不变。字符串下标从零开始。例如，对于字符串 'qwerty'： - 它的 $1$-排序是字符串 'qwerty'（所有字符都在 $0$ 位置）； - 它的 $2$-排序是字符串 'qetwry'（字符 'q'、'e' 和 't' 在 $0$ 位置，字符 'w'、'r' 和 'y' 在 $1$ 位置）； - 它的 $3$-排序是字符串 'qrwtey'（'q' 和 'r' 在 $0$ 位置，'w' 和 't' 在 $1$ 位置，'e' 和 'y' 在 $2$ 位置）； - 它的 $4$-排序是字符串 'qtwyer'； - 它的 $5$-排序是字符串 'qywert'。 现在给定长度为 $n$ 的字符串 $S$ 和 $m$ 次对该字符串的洗牌操作。每次洗牌操作有两个整数参数 $k$ 和 $d$，该操作会这样变换字符串 $S$：对于每个 $i$ 从 $0$ 到 $n-k$，按递增顺序依次对子串 $S[i..i+k-1]$ 应用一次 $d$-排序。这里 $S[a..b]$ 表示从位置 $a$ 到 $b$（包括 $a$ 和 $b$）的子串。 每次洗牌操作后，你需要输出当前的字符串 $S$。

第一行输入一个非空字符串 $S$，长度为 $n$，只包含小写和大写英文字母以及数字 $0$ 到 $9$。 第二行输入一个整数 $m$，表示洗牌操作的个数（$1\leq m \cdot n \leq 10^{6}$）。 接下来的 $m$ 行中，每行包含两个整数 $k$ 和 $d$，表示一次操作（$1 \leq d \leq k \leq n$）。

每次操作后输出当前的字符串 $S$。

这里提供样例的详细说明。第一次修改参数为 $k=4$，$d=2$，也就是需要对每个长度为 $4$ 的子串依次进行 $2$-排序。字符串变化过程如下： qwerty $ \to $ qewrty $ \to $ qerwty $ \to $ qertwy 因此，第一次操作后字符串 $S$ 变为 'qertwy'。 第二次操作参数为 $k=6$，$d=3$，此时，整个字符串 $S$ 被 $3$-排序： qertwy $ \to $ qtewry 第三次操作参数为 $k=5$，$d=2$。 qtewry $ \to $ qertwy $ \to $ qetyrw 由 ChatGPT 5 翻译