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.BufferedWriter;
import java.util.InputMismatchException;
import java.io.InputStream;
import java.util.NoSuchElementException;
import java.io.OutputStreamWriter;
import java.math.BigInteger;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.Writer;
import java.io.IOException;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Egor Kulikov (egor@egork.net)
 */
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();
	}
}

class TaskD {
    int[] period;
    int[][] answer;

    public void solve(int testNumber, InputReader in, OutputWriter out) {
        int count = in.readInt();
        period = IOUtils.readIntArray(in, count);
        answer = new int[60][count << 2];
        init(0, 0, count);
        int queryCount = in.readInt();
        for (int i = 0; i < queryCount; i++) {
            char type = in.readCharacter();
            if (type == 'C') {
                int at = in.readInt() - 1;
                period[at] = in.readInt();
                update(0, 0, count, at);
            } else {
                int from = in.readInt() - 1;
                int to = in.readInt() - 1;
                out.printLine(calculate(0, 0, count, from, to, 0));
            }
        }
    }

    private int calculate(int root, int from, int to, int left, int right, int shift) {
        if (from >= right || to <= left) {
            return -1;
        }
        if (from >= left && to <= right) {
            return shift + answer[shift % 60][root];
        }
        int middle = (from + to) >> 1;
        if (right <= middle) {
            return calculate(2 * root + 1, from, middle, left, right, shift);
        }
        if (left >= middle) {
            return calculate(2 * root + 2, middle, to, left, right, shift);
        }
        int result = calculate(2 * root + 1, from, middle, left, right, shift);
        return calculate(2 * root + 2, middle, to, left, right, result);
    }

    private void update(int root, int from, int to, int at) {
        if (from > at || to <= at) {
            return;
        }
        if (from + 1 == to) {
            for (int i = 0; i < 60; i++) {
                if (i % period[from] == 0) {
                    answer[i][root] = 2;
                } else {
                    answer[i][root] = 1;
                }
            }
        } else {
            int middle = (from + to) >> 1;
            update(2 * root + 1, from, middle, at);
            update(2 * root + 2, middle, to, at);
            for (int i = 0; i < 60; i++) {
                answer[i][root] = answer[i][2 * root + 1] + answer[(i + answer[i][2 * root + 1]) % 60][2 * root + 2];
            }
        }
    }

    private void init(int root, int from, int to) {
        if (from + 1 == to) {
            for (int i = 0; i < 60; i++) {
                if (i % period[from] == 0) {
                    answer[i][root] = 2;
                } else {
                    answer[i][root] = 1;
                }
            }
        } else {
            int middle = (from + to) >> 1;
            init(2 * root + 1, from, middle);
            init(2 * root + 2, middle, to);
            for (int i = 0; i < 60; i++) {
                answer[i][root] = answer[i][2 * root + 1] + answer[(i + answer[i][2 * root + 1]) % 60][2 * root + 2];
            }
        }
    }
}

class InputReader {

	private InputStream stream;
	private byte[] buf = new byte[1024];
	private int curChar;
	private int numChars;
	private 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);
	}
}

class OutputWriter {
	private final PrintWriter writer;

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

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

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

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;
	}

}

