C. Странная сортировка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Много ли сортировок вы знаете? По возрастанию, по убыванию, по длине, по полярному углу... Познакомимся с еще одной: d-сортировкой. Эта сортировка применяется к строкам длины не менее, чем d, где d — некоторое целое положительное число. Символы в строке упорядочиваются следующим образом: сначала идут все 0-е символы исходной строки, потом 1-е, потом 2-е и так далее, в конце будут стоять все (d - 1)-е символы исходной строки. Под i-ми символами здесь подразумеваются символы, позиции которых при делении на d дают в остатке i. При этом, если два символа стоят на позициях с одинаковым остатком, то их относительный порядок после сортировки не меняется. Индексация в строке выполняется с нуля. Например, для строки «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».

Вам дана строка S длины n и m операций перемешивания этой строки. Каждая операция перемешивания задается двумя целыми числами k и d и изменяет строку S следующим образом. Для каждого i от 0 до n - k в порядке возрастания к подстроке S[i..i + k - 1] применяется операция d-сортировки. Здесь под S[a..b] подразумевается подстрока, состоящая из символов на позициях от a до b включительно.

После каждой операции перемешивания вам необходимо вывести строку S.

Входные данные

В первой строке ввода содержится непустая строка S длины n, состоящая из строчных и заглавных букв латинского алфавита и цифр от 0 до 9.

Во второй строке ввода содержится целое число m – количество операций перемешивания (1 ≤ m·n ≤ 106).

Далее в m строках идут описания операций в виде пары чисел k и d (1 ≤ d ≤ k ≤ n).

Выходные данные

После каждой операции выведите текущее состояние строки S.

Примеры
Входные данные
qwerty
3
4 2
6 3
5 2
Выходные данные
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