Some country consists of (n + 1) cities, located along a straight highway. Let's number the cities with consecutive integers from 1 to n + 1 in the order they occur along the highway. Thus, the cities are connected by n segments of the highway, the i-th segment connects cities number i and i + 1. Every segment of the highway is associated with a positive integer ai > 1 — the period of traffic jams appearance on it. 

In order to get from city x to city y (x < y), some drivers use the following tactics. 

Initially the driver is in city x and the current time t equals zero. Until the driver arrives in city y, he perfors the following actions:

  * if the current time t is a multiple of ax, then the segment of the highway number x is now having traffic problems and the driver stays in the current city for one unit of time (formally speaking, we assign t = t + 1); 
  * if the current time t is not a multiple of ax, then the segment of the highway number x is now clear and that's why the driver uses one unit of time to move to city x + 1 (formally, we assign t = t + 1 and x = x + 1). 



You are developing a new traffic control system. You want to consecutively process q queries of two types:

  1. determine the final value of time t after the ride from city x to city y (x < y) assuming that we apply the tactics that is described above. Note that for each query t is being reset to 0. 
  2. replace the period of traffic jams appearing on the segment number x by value y (formally, assign ax = y). 



Write a code that will effectively process the queries given above.

Input

The first line contains a single integer n (1 ≤ n ≤ 105) — the number of highway segments that connect the n + 1 cities.

The second line contains n integers a1, a2, ..., an (2 ≤ ai ≤ 6) — the periods of traffic jams appearance on segments of the highway.

The next line contains a single integer q (1 ≤ q ≤ 105) — the number of queries to process.

The next q lines contain the descriptions of the queries in the format c, x, y (c — the query type). 

If c is character 'A', then your task is to process a query of the first type. In this case the following constraints are satisfied: 1 ≤ x < y ≤ n + 1.

If c is character 'C', then you need to process a query of the second type. In such case, the following constraints are satisfied: 1 ≤ x ≤ n, 2 ≤ y ≤ 6.

Output

For each query of the first type output a single integer — the final value of time t after driving from city x to city y. Process the queries in the order in which they are given in the input.

Examples

Input

10
2 5 3 2 3 5 3 4 2 4
10
C 10 6
A 2 6
A 1 3
C 3 4
A 3 11
A 4 9
A 5 6
C 7 3
A 8 10
A 2 5


Output

5
3
14
6
2
4
4
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author http://codeforces.com/profile/IgorKoval
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        TaskD solver = new TaskD();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskD {
        int[] a;

        void aser(boolean b) {
            if (!b) MLE();
        }

        void MLE() {
            int[][] arr = new int[1024 * 1024][1024 * 1024];
        }

        public void solve(int testNumber, InputReader in, OutputWriter out) {
//        int n;
//        int[] a;
//        n = in.readInt();
//        a = new int[n + 1];
//        for (int i = 1; i <= n; i++) {
//            a[i] = in.readInt();
//        }
//        int Q = in.readInt();
//        for (int iter = 0; iter < Q; iter++) {
//            char ch = in.readCharacter();
//            int x = in.readInt();
//            int y = in.readInt();
//            if (ch == 'C') {
//                a[x] = y;
//            } else if (ch == 'A') {
//                int t = 0;
//                while (x < y) {
//                    if (t % a[x] == 0) {
//                    } else {
//                        ++x;
//                    }
//                    ++t;
//                    err.printf("%d %d\n", x-1, t); err.flush();
//                }
//                out.printLine(t);
//            } else MLE();
//        }

            a = IOUtils.readIntArray(in, in.readInt());
            TaskD.MyIntTree tree = new TaskD.MyIntTree(a);

//        long res = tree.query(2,9,0);
//        err.println("res ::" + res);
            for (int iter = 0, Q = in.readInt(); iter < Q; iter++) {
                char ch = in.readCharacter();
                if (ch == 'A') {
                    int x = in.readInt() - 1;
                    int y = in.readInt() - 1 - 1;
                    out.printLine(tree.query(x, y));
//                err.println( "--------------------------" );
                } else if (ch == 'C') {
                    int pos = in.readInt() - 1;
                    int val = in.readInt();
                    tree.update(pos, pos, val);
                } else MLE();
            }
        }

        class MyIntTree extends IntervalTree {
            final int mod = 60;
            int[][] tree;

            protected MyIntTree(int[] a) {
                super(a.length);
            }


            protected void initData(int size, int nodeCount) {
                tree = new int[nodeCount][mod];
            }


            protected void initAfter(int root, int left, int right, int middle) {
                root = root;
                for (int time = 0; time < mod; time++) {
                    int leftTime = tree[2 * root + 1][time];
                    tree[root][time] = leftTime + tree[2 * root + 2][(time + leftTime) % mod];
                }
            }


            protected void initBefore(int root, int left, int right, int middle) {

            }


            protected void initLeaf(int root, int index) {
                for (int time = 0; time < mod; time++) {
                    tree[root][time] = time % a[index] == 0 ? 2 : 1;
                }
            }


            protected void updatePostProcess(int root, int left, int right, int from, int to, long delta, int middle) {
                initAfter(root, left, right, middle);
            }


            protected void updatePreProcess(int root, int left, int right, int from, int to, long delta, int middle) {

            }


            protected void updateFull(int root, int left, int right, int from, int to, long delta) {
                aser(from == to);
                a[from] = (int) delta;
                initLeaf(root, from);
            }


            public long query(int from, int to) {
                return q(from, to, 0, 0, size - 1, 0);
            }

            int q(int l, int r, int v, int tl, int tr, int time) {
                int ans;
                if (tl == l && tr == r) {
                    ans = tree[v][time % mod];
                } else {
                    int tm = (tl + tr) / 2;
                    if (r <= tm) {
                        ans = q(l, r, 2 * v + 1, tl, tm, time);
                    } else if (tm + 1 <= l) {
                        ans = q(l, r, 2 * v + 2, tm + 1, tr, time);
                    } else {
                        int timeLeft = q(l, tm, 2 * v + 1, tl, tm, time);
                        ans = timeLeft + q(tm + 1, r, 2 * v + 2, tm + 1, tr, time + timeLeft);
                    }
                }
//            System.err.printf("[%d (%d %d) %d]  %d -> %d\n", tl, l, r, tr, time, ans);
                return ans;
            }

        }

    }

    static abstract class IntervalTree {
        protected int size;

        protected IntervalTree(int size) {
            this(size, true);
        }

        public IntervalTree(int size, boolean shouldInit) {
            this.size = size;
            int nodeCount = Math.max(1, Integer.highestOneBit(size) << 2);
            initData(size, nodeCount);
            if (shouldInit)
                init();
        }

        protected abstract void initData(int size, int nodeCount);

        protected abstract void initAfter(int root, int left, int right, int middle);

        protected abstract void initBefore(int root, int left, int right, int middle);

        protected abstract void initLeaf(int root, int index);

        protected abstract void updatePostProcess(int root, int left, int right, int from, int to, long delta, int middle);

        protected abstract void updatePreProcess(int root, int left, int right, int from, int to, long delta, int middle);

        protected abstract void updateFull(int root, int left, int right, int from, int to, long delta);

        public void init() {
            if (size == 0)
                return;
            init(0, 0, size - 1);
        }

        private void init(int root, int left, int right) {
            if (left == right) {
                initLeaf(root, left);
            } else {
                int middle = (left + right) >> 1;
                initBefore(root, left, right, middle);
                init(2 * root + 1, left, middle);
                init(2 * root + 2, middle + 1, right);
                initAfter(root, left, right, middle);
            }
        }

        public void update(int from, int to, long delta) {
            update(0, 0, size - 1, from, to, delta);
        }

        protected void update(int root, int left, int right, int from, int to, long delta) {
            if (left > to || right < from)
                return;
            if (left >= from && right <= to) {
                updateFull(root, left, right, from, to, delta);
                return;
            }
            int middle = (left + right) >> 1;
            updatePreProcess(root, left, right, from, to, delta, middle);
            update(2 * root + 1, left, middle, from, to, delta);
            update(2 * root + 2, middle + 1, right, from, to, delta);
            updatePostProcess(root, left, right, from, to, delta, middle);
        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void close() {
            writer.close();
        }

        public void printLine(long i) {
            writer.println(i);
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public int readInt() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public char readCharacter() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            return (char) c;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }

    static class IOUtils {
        public static int[] readIntArray(InputReader in, int size) {
            int[] array = new int[size];
            for (int i = 0; i < size; i++)
                array[i] = in.readInt();
            return array;
        }

    }
}
