Problem: 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.

Input

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). 

Output

After each operation print the current state of string S.

Examples

Input

qwerty
3
4 2
6 3
5 2


Output

qertwy
qtewry
qetyrw

Note

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

Solution (in JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.util.Arrays;
import java.io.IOException;
import java.io.UncheckedIOException;
import java.io.Closeable;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) throws Exception {
        Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 29);
        thread.start();
        thread.join();
    }

    static class TaskAdapter implements Runnable {
        @Override
        public void run() {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            FastInput in = new FastInput(inputStream);
            FastOutput out = new FastOutput(outputStream);
            CStrangeSorting solver = new CStrangeSorting();
            solver.solve(1, in, out);
            out.close();
        }
    }

    static class CStrangeSorting {
        public void solve(int testNumber, FastInput in, FastOutput out) {
            char[] s = new char[(int) 1e6];
            int n = in.rs(s);
            s = Arrays.copyOf(s, n);
            char[] res = new char[n];
            int m = in.ri();
            int[] p1 = new int[n];
            int[] p2 = new int[n];
            int[] p3 = new int[n];
            for (int i = 0; i < n; i++) {
                p1[i] = i - 1;
                if (p1[i] < 0) {
                    p1[i] += n;
                }
            }
            for (int i = 0; i < m; i++) {
                int k = in.ri();
                int d = in.ri();
                int wpos = 0;
                for (int j = 0; j < d; j++) {
                    for (int t = j; t < k; t += d) {
                        p2[t] = wpos++;
                    }
                }
                for (int j = k; j < n; j++) {
                    p2[j] = j;
                }
                for (int j = 0; j < n; j++) {
                    p3[j] = p1[p2[j]];
                }
                Permutation perm = new Permutation(p3);
                for (int j = 0; j < n; j++) {
                    int to = perm.apply(j, n - k + 1) - (k - 1);
                    if (to < 0) {
                        to += n;
                    }
                    res[to] = s[j];
                }
                char[] tmp = res;
                res = s;
                s = tmp;
                out.println(s);
            }
        }

    }

    static class FastInput {
        private final InputStream is;
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastInput(InputStream is) {
            this.is = is;
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    bufLen = -1;
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }

        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }

        public int ri() {
            return readInt();
        }

        public int readInt() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            int val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

        public int rs(char[] data, int offset) {
            return readString(data, offset);
        }

        public int rs(char[] data) {
            return rs(data, 0);
        }

        public int readString(char[] data, int offset) {
            skipBlank();

            int originalOffset = offset;
            while (next > 32) {
                data[offset++] = (char) next;
                next = read();
            }

            return offset - originalOffset;
        }

    }

    static class Permutation {
        int[] g;
        int[] idx;
        int[] l;
        int[] r;
        int n;

        public Permutation(int[] p) {
            this(p, p.length);
        }

        public Permutation(int[] p, int len) {
            n = len;
            boolean[] visit = new boolean[n];
            g = new int[n];
            l = new int[n];
            r = new int[n];
            idx = new int[n];
            int wpos = 0;
            for (int i = 0; i < n; i++) {
                int val = p[i];
                if (visit[val]) {
                    continue;
                }
                visit[val] = true;
                g[wpos] = val;
                l[wpos] = wpos;
                idx[val] = wpos;
                wpos++;
                while (true) {
                    int x = p[g[wpos - 1]];
                    if (visit[x]) {
                        break;
                    }
                    visit[x] = true;
                    g[wpos] = x;
                    l[wpos] = l[wpos - 1];
                    idx[x] = wpos;
                    wpos++;
                }
                for (int j = l[wpos - 1]; j < wpos; j++) {
                    r[j] = wpos - 1;
                }
            }
        }

        public int apply(int x, int p) {
            int i = idx[x];
            int dist = DigitUtils.mod((i - l[i]) + p, r[i] - l[i] + 1);
            return g[dist + l[i]];
        }

        public String toString() {
            StringBuilder builder = new StringBuilder();
            for (int i = 0; i < n; i++) {
                builder.append(apply(i, 1)).append(' ');
            }
            return builder.toString();
        }

    }

    static class DigitUtils {
        private DigitUtils() {
        }

        public static int mod(int x, int mod) {
            if (x < -mod || x >= mod) {
                x %= mod;
            }
            if (x < 0) {
                x += mod;
            }
            return x;
        }

    }

    static class FastOutput implements AutoCloseable, Closeable, Appendable {
        private static final int THRESHOLD = 32 << 10;
        private final Writer os;
        private StringBuilder cache = new StringBuilder(THRESHOLD * 2);

        public FastOutput append(CharSequence csq) {
            cache.append(csq);
            return this;
        }

        public FastOutput append(CharSequence csq, int start, int end) {
            cache.append(csq, start, end);
            return this;
        }

        private void afterWrite() {
            if (cache.length() < THRESHOLD) {
                return;
            }
            flush();
        }

        public FastOutput(Writer os) {
            this.os = os;
        }

        public FastOutput(OutputStream os) {
            this(new OutputStreamWriter(os));
        }

        public FastOutput append(char c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput append(String c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput append(char[] c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput println(char[] c) {
            return append(c).println();
        }

        public FastOutput println() {
            return append(System.lineSeparator());
        }

        public FastOutput flush() {
            try {
//            boolean success = false;
//            if (stringBuilderValueField != null) {
//                try {
//                    char[] value = (char[]) stringBuilderValueField.get(cache);
//                    os.write(value, 0, cache.length());
//                    success = true;
//                } catch (Exception e) {
//                }
//            }
//            if (!success) {
                os.append(cache);
//            }
                os.flush();
                cache.setLength(0);
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
            return this;
        }

        public void close() {
            flush();
            try {
                os.close();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }

        public String toString() {
            return cache.toString();
        }

    }
}