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.*;
import java.util.*;

public class trafficjamsinland {
  private static Reader in;
  private static PrintWriter out;
  public static int BLOCK_SIZE = 300;
  public static int NUM_BLOCKS;
  public static int LCM = 60;
  public static int N, Q;
  public static int[][] ty, tc;
  public static int[] a;

  public static void main(String[] args) throws IOException {
    long start = System.currentTimeMillis();
    in = new Reader();
    out = new PrintWriter(System.out, true);
    N = in.nextInt();
    a = new int[N];
    for (int i = 0; i < N; i++) 
      a[i] = in.nextInt();
    NUM_BLOCKS = N / BLOCK_SIZE + 1;
    ty = new int[NUM_BLOCKS][LCM];
    tc = new int[NUM_BLOCKS][LCM];
    for (int i = 0; i < NUM_BLOCKS; i++) {
      fixBlock(i);
    }
    
    Q = in.nextInt();
    StringBuffer buff = new StringBuffer();
    while (Q-- > 0) {
      char cmd = in.nextChar();
      if (cmd == 'C') {
        int x = in.nextInt()-1;
        int y = in.nextInt();
        a[x] = y;
        fixBlock(x / BLOCK_SIZE);
      } else {
        int from = in.nextInt()-1, to = in.nextInt()-2;
        int idx1 = from / BLOCK_SIZE;
        int idx2 = to / BLOCK_SIZE;
        if (idx1 == idx2) {
          buff.append(slowSolve(from, to, 0) + "\n");
          continue;
        }
        
        int res = 0;
        int m = slowSolve(from, (idx1+1) * BLOCK_SIZE-1, 0);
        res += m;
        m %= LCM;
        for (int j = idx1+1; j < idx2; j++) {
          if (tc[j][m] == -1) {
            fix(j, m);
          }
          res += tc[j][m];
          m = ty[j][m];
        }
        res += slowSolve(idx2 * BLOCK_SIZE, to, m);
        
        buff.append(res+"\n");
      }
    }
    out.println(buff);
    out.close();
    System.exit(0);
  }
  
  public static void fix(int j, int m) {
    int start = j * BLOCK_SIZE;
    if (start >= N) {
      tc[j][m] = 0;
      ty[j][m] = 0;
      return;
    }
    int end = Math.min(N-1, start + BLOCK_SIZE-1);
    int r = slowSolve(start, end, m);
    ty[j][m] = (r + m) % LCM;
    tc[j][m] = r;
  }

  public static void fixBlock(int block) {
    int start = block * BLOCK_SIZE;
    if (start >= N) return;
    int end = Math.min(N-1, start + BLOCK_SIZE - 1);
    Arrays.fill(ty[block], -1);
    Arrays.fill(tc[block], -1);
//    for (int i = 0; i < LCM; i++) {
//      int r = slowSolve(start, end, i);
//      ty[block][i] = (r + i) % LCM;
//      tc[block][i] = r;
//    }
  }
  
  public static int slowSolve(int from, int to, int b) {
    int ct = 0;
    for (int j = from; j <= to; j++) {
      if ((ct + b) % a[j] == 0) ct++;
      ct++;
    }
    return ct;
  }

  static class Reader {
    final private int BUFFER_SIZE = 1 << 16;
    private DataInputStream din;
    private byte[] buffer;
    private int bufferPointer, bytesRead;

    public Reader() {
      din = new DataInputStream(System.in);
      buffer = new byte[BUFFER_SIZE];
      bufferPointer = bytesRead = 0;
    }

    public Reader(String file_name) throws IOException {
      din = new DataInputStream(new FileInputStream(file_name));
      buffer = new byte[BUFFER_SIZE];
      bufferPointer = bytesRead = 0;
    }

    public String readLine() throws IOException {
      byte[] buf = new byte[1024];
      int cnt = 0;
      byte c = read();
      while (c <= ' ')
        c = read();
      do {
        buf[cnt++] = c;
      } while ((c = read()) != '\n');
      return new String(buf, 0, cnt);
    }

    public String next() throws IOException {
      byte[] buf = new byte[1024];
      int cnt = 0;
      byte c = read();
      while (c <= ' ')
        c = read();
      do {
        buf[cnt++] = c;
      } while ((c = read()) > ' ');
      return new String(buf, 0, cnt);
    }
    
    public char nextChar() throws IOException {
      byte c = read();
      while (c <= ' ')
        c = read();
      return (char)c;
    }

    public int nextInt() throws IOException {
      int ret = 0;
      byte c = read();
      while (c <= ' ')
        c = read();
      boolean neg = (c == '-');
      if (neg)
        c = read();
      do {
        ret = ret * 10 + c - '0';
      } while ((c = read()) >= '0' && c <= '9');
      if (neg)
        return -ret;
      return ret;
    }

    public long nextLong() throws IOException {
      long ret = 0;
      byte c = read();
      while (c <= ' ')
        c = read();
      boolean neg = (c == '-');
      if (neg)
        c = read();
      do {
        ret = ret * 10 + c - '0';
      } while ((c = read()) >= '0' && c <= '9');
      if (neg)
        return -ret;
      return ret;
    }

    public double nextDouble() throws IOException {
      double ret = 0, div = 1;
      byte c = read();
      while (c <= ' ')
        c = read();
      boolean neg = (c == '-');
      if (neg)
        c = read();
      do {
        ret = ret * 10 + c - '0';
      } while ((c = read()) >= '0' && c <= '9');
      if (c == '.')
        while ((c = read()) >= '0' && c <= '9')
          ret += (c - '0') / (div *= 10);
      if (neg)
        return -ret;
      return ret;
    }

    private void fillBuffer() throws IOException {
      bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
      if (bytesRead == -1)
        buffer[0] = -1;
    }

    private byte read() throws IOException {
      if (bufferPointer == bytesRead)
        fillBuffer();
      return buffer[bufferPointer++];
    }

    public void close() throws IOException {
      if (din == null)
        return;
      din.close();
    }
  }


}
