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
#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:100000000")
using namespace std;
template <class T>
void read(T &x) {
  char c, mi = 0;
  while (c = getchar(), c <= 32)
    ;
  if (c == '-')
    mi = 1, x = 0;
  else if (c < 48 || c > 57)
    return void(x = c);
  else
    x = c - 48;
  while (c = getchar(), c > 32) x = 10 * x + c - 48;
  if (mi == 1) x = -x;
}
template <class T>
void read(T &x, T &y) {
  read(x);
  read(y);
}
template <class T>
void read(T &x, T &y, T &z) {
  read(x, y);
  read(z);
}
template <class T>
void reada(T *a, int n) {
  for (int i = 0; i < n; ++i) read(a[i]);
}
template <class T>
void write(T x) {
  static char s[20];
  char pt = 0, mi = (x < 0);
  if (mi == 1) x = -x;
  while (!pt || x > 0) {
    s[++pt] = (char)(x % 10 + '0');
    x /= 10;
  }
  if (mi == 1) putchar('-');
  while (pt > 0) putchar(s[pt--]);
}
template <class T>
void write(T x, T y) {
  write(x);
  putchar(' ');
  write(y);
}
template <class T>
void write(T x, T y, T z) {
  write(x, y);
  putchar(' ');
  write(z);
}
template <class T>
void writeln(T x) {
  write(x);
  puts("");
}
template <class T>
void writea(T *a, int n) {
  for (int i = 0; i < n; ++i) {
    write(a[i]);
    putchar(i + 1 == n ? '\n' : ' ');
  }
}
template <class T>
T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}
template <class T>
T lcm(T a, T b) {
  return a / gcd(a, b) * b;
}
template <class T>
T qpom(T a, T b, T mod = 1000000007) {
  T r = 1;
  while (b > 0) {
    if (b & 1) r = r * a % mod;
    a = a * a % mod;
    b /= 2;
  }
  return r;
}
template <class T>
T qpow(T a, T b) {
  T r = 1;
  while (b > 0) {
    if (b & 1) r *= a;
    a *= a;
    b /= 2;
  }
  return r;
}
template <class T>
T imin(T a, T b) {
  return a < b ? a : b;
}
template <class T>
T imax(T a, T b) {
  return a > b ? a : b;
}
template <class T>
inline void rmin(T &a, const T &b) {
  if (a > b) a = b;
}
template <class T>
inline void rmax(T &a, const T &b) {
  if (a < b) a = b;
}
template <class T>
T sqr(const T &a) {
  return a * a;
}
const int SIZE = 60;
struct Node {
  int a[SIZE];
  int pt;
  void f(const Node &L, const Node &R) {
    for (int i = 0; i < SIZE; ++i) {
      a[i] = L.a[i] + R.a[(i + L.a[i]) % SIZE];
    }
  }
  void g(int x) {
    for (int i = 0; i < SIZE; ++i) {
      a[i] = 1 + (i % x == 0);
    }
  }
} t[4 * 100010];
int n, q, a[100010];
char c;
void Build(int v, int l, int r) {
  if (l != r) {
    Build(v + v, l, (l + r) / 2);
    Build(v + v + 1, (l + r) / 2 + 1, r);
    t[v].f(t[v + v], t[v + v + 1]);
  } else {
    t[v].g(a[l]);
  }
}
void Update(int v, int l, int r, int pos, int val) {
  if (l != r) {
    int m = (l + r) / 2;
    if (pos <= m) {
      Update(v + v, l, m, pos, val);
    } else {
      Update(v + v + 1, m + 1, r, pos, val);
    }
    t[v].f(t[v + v], t[v + v + 1]);
  } else {
    t[v].g(val);
  }
}
void Update(int pos, int val) { Update(1, 1, n, pos, val); }
int Get(int v, int L, int R, int l, int r, int timer) {
  if (L == l && r == R) {
    return timer + t[v].a[timer % SIZE];
  }
  int M = (L + R) / 2;
  if (r <= M) {
    return Get(v + v, L, M, l, r, timer);
  }
  if (l > M) {
    return Get(v + v + 1, M + 1, R, l, r, timer);
  }
  return Get(v + v + 1, M + 1, R, M + 1, r, Get(v + v, L, M, l, M, timer));
}
int Get(int x, int y) { return Get(1, 1, n, x, y - 1, 0); }
int main() {
  read(n);
  reada(a + 1, n);
  Build(1, 1, n);
  read(q);
  while (q-- > 0) {
    char c;
    int x, y;
    read(c);
    read(x, y);
    if (c == 'C') {
      Update(x, y);
    } else {
      writeln(Get(x, y));
    }
  }
  getchar();
  getchar();
  return 0;
}
