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 conta