← 返回题目列表

Codeforces · 484/C

C. 奇怪的排序

中文机器翻译题面 查看原题

具体命令你知道多少?升序、降序、长度升序、极角升序……我们再看看另一种具体的顺序:d排序。这种排序适用于长度至少为 d 的字符串,其中 d 是某个正整数。字符串的字符按以下方式排序:首先是初始字符串的所有第 0 个字符,然后是第 1 个字符,然后是第 2 个字符,依此类推,最后是初始字符串的所有第 (d - 1) 个字符。第 i 个字符是指位置正好是 i 模 d 的所有字符。如果两个字符处于整数除以 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。对于按升序从 0 到 n - k 的每个 i,我们将 d 排序操作应用于子串 S[i..i + k - 1]。这里 S[a..b] 表示由 a 到 b 位置上的字符组成的子字符串。

每次打乱操作后,您需要打印字符串 S。

输入

输入的第一行包含一个长度为n的非空字符串S,由大小写英文字母和0到9的数字组成。

输入的第二行包含整数 m – 洗牌操作的数量 (1 ≤ m·n ≤ 106)。

接下来的 m 行包含由两个整数 k 和 d (1 ≤ d ≤ k ≤ n) 组成的运算的描述。

输出

每次操作后打印字符串 S 的当前状态。

示例

输入 #1

qwerty
3
4 2
6 3
5 2

输出 #1

qertwy
qtewry
qetyrw

注意

这是示例的详细说明。第一个修改是使用参数 k = 4、d = 2 执行的。这意味着您需要对每个长度为 4 的子字符串从左到右逐一应用 2 排序。该字符串将按以下方式转换:

qwerty → qewrty → qerwty → qertwy

因此,字符串 S 在第一个查询末尾等于“qertwy”。

第二个修改是使用参数 k = 6、d = 3 执行的。此操作的结果是整个字符串 S 被其 3 排序替换:

qertwy → qtewry

第三次修改是使用参数 k = 5、d = 2 执行的。

qtewry → qertwy → qetyrw