Strange Sorting

题面翻译

对一个长度至少为 $d$ 的字符串（下标从0开始），定义 $d-sorting$ 的排序方式为，循环 $i$ 从 $0$ 到 $(d-1)$，将字符串中下标 $MOD\ d$ 为 $i$ 的字符按原顺序取出来依次加到末尾。
例：$abcde$ 的 $2-sorting$ 结果为 $acebd$。
给定长度为 $n$ 的字符串，$m$ 次操作，每次将所有长度为 $k$ 的子串按左到右的顺序进行一次 $d-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$ .

输入格式

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<=10^{6}$ ).

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

输出格式

After each operation print the current state of string $S$ .

样例 #1

样例输入 #1

qwerty
3
4 2
6 3
5 2

样例输出 #1

qertwy
qtewry
qetyrw

提示

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