CF484C.Strange Sorting

How many specific orders do you know? Ascending order, descending order, order of ascending length, order of ascending polar angle... Let's have a look at another specific order: d-sorting. This sorting is applied to the strings of length at least d, where d is some positive integer. The characters of the string are sorted in following manner: first come all the 0-th characters of the initial string, then the 1-st ones, then the 2-nd ones and so on, in the end go all the (d - 1)-th characters of the initial string. By the i-th characters we mean all the character whose positions are exactly i modulo d. If two characters stand on the positions with the same remainder of integer division by d, their relative order after the sorting shouldn't be changed. The string is zero-indexed. For example, for string 'qwerty':

Its 1-sorting is the string 'qwerty' (all characters stand on 0 positions),

Its 2-sorting is the string 'qetwry' (characters 'q', 'e' and 't' stand on 0 positions and characters 'w', 'r' and 'y' are on 1 positions),

Its 3-sorting is the string 'qrwtey' (characters 'q' and 'r' stand on 0 positions, characters 'w' and 't' stand on 1 positions and characters 'e' and 'y' stand on 2 positions),

Its 4-sorting is the string 'qtwyer',

Its 5-sorting is the string 'qywert'.

You are given string S of length n and m shuffling operations of this string. Each shuffling operation accepts two integer arguments k and d and transforms string S as follows. For each i from 0 to n - k in the increasing order we apply the operation of d-sorting to the substring S[i..i + k - 1]. Here S[a..b] represents a substring that consists of characters on positions from a to b inclusive.

After each shuffling operation you need to print string S.

你知道多少种特定的排序方式？升序、降序、按长度升序、按极角升序……我们再来看一种特定的排序方式：d-排序（d-sorting）。该排序适用于长度至少为 $ d $ 的字符串，其中 $ d $ 是某个正整数。字符串中字符的排序方式如下：首先放置原字符串中所有下标模 $ d $ 余 $ 0 $ 的字符（即所有第 $ 0 $ 类字符），然后是所有下标模 $ d $ 余 $ 1 $ 的字符（即所有第 $ 1 $ 类字符），接着是所有下标模 $ d $ 余 $ 2 $ 的字符（即所有第 $ 2 $ 类字符），依此类推，最后放置所有下标模 $ d $ 余 $ d-1 $ 的字符（即所有第 $ d-1 $ 类字符）。这里所说的“第 $ i $ 类字符”，指的是所有位置下标对 $ d $ 取模结果恰好为 $ i $ 的字符。若两个字符的位置对 $ d $ 取模后余数相同，则它们在排序后的相对顺序应保持不变。字符串采用从 0 开始编号。例如，对于字符串 'qwerty'：

• 它的 1-排序 结果是 'qwerty'（所有字符的位置均模 $ 1 $ 余 $ 0 $）；
• 它的 2-排序 结果是 'qetwry'（字符 'q'、'e' 和 't' 位于模 $ 2 $ 余 $ 0 $ 的位置，字符 'w'、'r' 和 'y' 位于模 $ 2 $ 余 $ 1 $ 的位置）；
• 它的 3-排序 结果是 'qrwtey'（字符 'q' 和 'r' 位于模 $ 3 $ 余 $ 0 $ 的位置，字符 'w' 和 't' 位于模 $ 3 $ 余 $ 1 $ 的位置，字符 'e' 和 'y' 位于模 $ 3 $ 余 $ 2 $ 的位置）；
• 它的 4-排序 结果是 'qtwyer'；
• 它的 5-排序 结果是 'qywert'。

给定一个长度为 $ n $ 的字符串 $ S $，以及 $ m $ 次对该字符串进行的洗牌操作（shuffling operation）。每次洗牌操作接受两个整数参数 $ k $ 和 $ d $，并按如下方式变换字符串 $ S $：对每个 $ i $（从 $ 0 $ 到 $ n - k $，按递增顺序），对子串 $ S[i..i + k - 1] $ 执行一次 $ d $-排序操作。其中，$ S[a..b] $ 表示由位置从 $ a $ 到 $ b $（含端点）的所有字符组成的子串。

每次洗牌操作完成后，你需要输出当前字符串 $ S $。

The first line of the input contains a non-empty string S of length n, consisting of lowercase and uppercase English letters and digits from 0 to 9.

The second line of the input contains integer m – the number of shuffling operations (1 ≤ m·n ≤ 106).

Following m lines contain the descriptions of the operations consisting of two integers k and d (1 ≤ d ≤ k ≤ n).

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

输入的第二行包含一个整数 $m$ —— 洗牌操作的次数（满足 $1 \leq m \cdot n \leq 10^6$）。

接下来的 $m$ 行每行包含一个操作的描述，由两个整数 $k$ 和 $d$ 组成（满足 $1 \leq d \leq k \leq n$）。

After each operation print the current state of string S.

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

Here is detailed explanation of the sample. The first modification is executed with arguments k = 4, d = 2. That means that you need to apply 2-sorting for each substring of length 4 one by one moving from the left to the right. The string will transform in the following manner:

qwerty  →  qewrty  →  qerwty  →  qertwy

Thus, string S equals 'qertwy' at the end of first query.

The second modification is executed with arguments k = 6, d = 3. As a result of this operation the whole string S is replaced by its 3-sorting:

qertwy  →  qtewry

The third modification is executed with arguments k = 5, d = 2.

qtewry  →  qertwy  →  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