CF498D.Traffic Jams in the Land

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 a__i > 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 a__x, 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 a__x, 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 a__x = y).

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

某个国家由 $n+1$ 座城市组成，这些城市沿一条笔直的高速公路依次排列。我们按它们在高速公路上出现的顺序，用连续整数 $1$ 到 $n+1$ 对这些城市编号。因此，这些城市由 $n$ 段高速公路连接，其中第 $i$ 段高速公路连接第 $i$ 号城市与第 $i+1$ 号城市。每一段高速公路均关联一个正整数 $a_i > 1$ —— 即该路段发生交通拥堵的周期。

为从城市 $x$ 到达城市 $y$（其中 $x < y$），部分司机采用如下策略：

初始时，司机位于城市 $x$，当前时间 $t$ 为 $0$。在司机抵达城市 $y$ 前，他反复执行以下操作：

• 若当前时间 $t$ 是 $a_x$ 的倍数，则第 $x$ 号高速公路路段当前正发生交通拥堵，司机在当前城市停留一单位时间（形式化地，令 $t = t + 1$）；
• 若当前时间 $t$ 不是 $a_x$ 的倍数，则第 $x$ 号高速公路路段当前畅通，司机花费一单位时间驶向城市 $x+1$（形式化地，令 $t = t + 1$ 且 $x = x + 1$）。

你正在开发一套新型交通控制系统。你需要依次处理 $q$ 个查询，查询分为两类：

1. 计算从城市 $x$ 到城市 $y$（其中 $x < y$）按上述策略行驶后最终的时间 $t$ 值。注意：对每个查询，$t$ 均重置为 $0$。
2. 将第 $x$ 号高速公路路段的交通拥堵周期更新为 $y$（形式化地，令 $a_x = y$）。

请编写一段高效处理上述查询的代码。

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 _a_1, _a_2, ..., a__n (2 ≤ a__i ≤ 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.

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）——表示连接 $n+1$ 座城市的高速公路路段数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$2 \leq a_i \leq 6$）——表示各高速公路路段上交通拥堵出现的周期。

接下来一行包含一个整数 $q$（$1 \leq q \leq 10^5$）——表示需要处理的查询数量。

接下来 $q$ 行，每行描述一个查询，格式为 $c$, $x$, $y$（其中 $c$ 为查询类型）。

若 $c$ 是字符 'A'，则需处理第一类查询。此时满足约束：$1 \leq x < y \leq n+1$。

若 $c$ 是字符 'C'，则需处理第二类查询。此时满足约束：$1 \leq x \leq n$，$2 \leq y \leq 6$。

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.

对于每个第一类查询，输出一个整数——从城市 $x$ 驾车前往城市 $y$ 后的最终时间 $t$。请按照输入中给出的顺序处理查询。