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.util.*;
import java.util.Map.Entry;
import java.io.*;
import java.awt.Point;
import java.math.BigInteger;

import static java.lang.Math.*;

public class CodeforcesD implements Runnable {

    final boolean ONLINE_JUDGE = System.getProperty("ONLINE_JUDGE") != null;

    BufferedReader in;
    PrintWriter out;
    StringTokenizer tok = new StringTokenizer("");

    void init() throws FileNotFoundException {
        if (ONLINE_JUDGE) {
            in = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);
        } else {
            in = new BufferedReader(new FileReader("input.txt"));
            out = new PrintWriter("output.txt");
        }
    }

    String readString() throws IOException {
        while (!tok.hasMoreTokens()) {
            try {
                tok = new StringTokenizer(in.readLine());
            } catch (Exception e) {
                return null;
            }
        }
        return tok.nextToken();
    }

    int readInt() throws IOException {
        return Integer.parseInt(readString());
    }

    long readLong() throws IOException {
        return Long.parseLong(readString());
    }

    double readDouble() throws IOException {
        return Double.parseDouble(readString());
    }

    int[] readIntArray(int n) throws IOException {
        int[] array = new int[n];
        for (int i = 0; i < n; i++)
            array[i] = readInt();
        return array;
    }

    public static void main(String[] args) {
        new Thread(null, new CodeforcesD(), "", 128 * (1L << 20)).start();
    }

    long timeBegin, timeEnd;

    void time() {
        timeEnd = System.currentTimeMillis();
        System.err.println("Time = " + (timeEnd - timeBegin));
    }

    long memoryTotal, memoryFree;

    void memory() {
        memoryFree = Runtime.getRuntime().freeMemory();
        System.err.println("Memory = " + ((memoryTotal - memoryFree) >> 10)
                + " KB");
    }

    void debug(Object... objects) {
        if (DEBUG) {
            for (Object o : objects) {
                System.err.println(o.toString());
            }
        }
    }

    public void run() {
        try {
            timeBegin = System.currentTimeMillis();
            memoryTotal = Runtime.getRuntime().freeMemory();
            init();
            solve();
            out.close();
            time();
            memory();
        } catch (Exception e) {
            e.printStackTrace(System.err);
            System.exit(-1);
        }
    }

    boolean DEBUG = false;

    class SegmentTree {
        int[][] t;
        int[] period;
        int n;

        public SegmentTree(int n, int[] period) {
            t = new int[60][n << 2];
            this.period = period;
            this.n = n;
            init(1, 0, n - 1);
        }

        void init(int v, int left, int right) {
            if (left == right) {
                for (int i = 0; i < 60; i++) {
                    if (i % period[left] == 0)
                        t[i][v] = 2;
                    else
                        t[i][v] = 1;
                }
            } else {
                int mid = (left + right) >> 1;
                init((v << 1), left, mid);
                init((v << 1) + 1, mid + 1, right);
                for (int i = 0; i < 60; i++) {
                    int leftTime = t[i][v << 1];
                    int ourTime = leftTime
                            + t[(i + leftTime) % 60][(v << 1) + 1];
                    t[i][v] = ourTime;
                }
            }
        }

        public void update(int idx, int value) {
            period[idx] = value;
            update(1, 0, n - 1, idx);
        }

        void update(int v, int left, int right, int idx) {
            if (left == right) {
                for (int i = 0; i < 60; i++) {
                    if (i % period[left] == 0)
                        t[i][v] = 2;
                    else
                        t[i][v] = 1;
                }
            } else {
                int mid = (left + right) >> 1;
                if (idx <= mid) {
                    update((v << 1), left, mid, idx);
                } else {
                    update((v << 1) + 1, mid + 1, right, idx);
                }
                for (int i = 0; i < 60; i++) {
                    int leftTime = t[i][v << 1];
                    int ourTime = leftTime
                            + t[(i + leftTime) % 60][(v << 1) + 1];
                    t[i][v] = ourTime;
                }
            }
        }

        public int get(int l, int r) {
            return get(1, 0, n - 1, l, r, 0);
        }

        int get(int v, int left, int right, int l, int r, int time) {
            if (l < left || r > right || l > r)
                return 0;
            if (l == left && r == right) {
                return t[time][v];
            }
            int mid = (left + right) >> 1;
            int leftTime = get((v << 1), left, mid, l, min(r, mid), time);
            int rightTime = get((v << 1) + 1, mid + 1, right, max(l, mid + 1),
                    r, (time + leftTime) % 60);
            return leftTime + rightTime;
        }
    }

    void solve() throws IOException {

        int n = readInt();
        int[] period = readIntArray(n);

        SegmentTree segmentTree = new SegmentTree(n, period);

        int q = readInt();

        while (q-- > 0) {
            String s = readString();
            if ("C".equals(s)) {
                int idx = readInt() - 1;
                int value = readInt();
                segmentTree.update(idx, value);
            } else {
                int l = readInt() - 1;
                int r = readInt() - 2;
                int res = segmentTree.get(l, r);
                out.println(res);
            }
        }

    }
}