某个国家由 (n + 1) 个城市组成,位于一条笔直的高速公路沿线。让我们按照城市沿高速公路出现的顺序,使用从 1 到 n + 1 的连续整数对城市进行编号。因此,城市由 n 段高速公路连接,第 i 段连接城市编号 i 和 i+1。高速公路的每一段都与一个正整数 ai > 1 相关联 - 其上出现交通拥堵的时间段。
为了从城市 x 到城市 y (x < y),一些司机使用以下策略。
最初,驾驶员位于城市 x,当前时间 t 为零。直到司机到达y城市,他执行以下操作:
- 如果当前时间 t 是 ax 的倍数,则编号为 x 的高速公路路段现在出现交通问题,并且驾驶员在当前城市停留了一个单位时间(形式上来说,我们指定 t = t + 1);
- 如果当前时间 t 不是 ax 的倍数,则高速公路编号 x 的路段现在是清晰的,这就是驾驶员使用一个单位时间移动到城市 x + 1 的原因(正式地,我们指定 t = t + 1 和 x = x + 1)。
您正在开发一种新的交通控制系统。您想要连续处理两种类型的 q 个查询:
1. 假设我们应用上述策略,确定从城市 x 骑行到城市 y 后时间 t 的最终值 (x < y)。请注意,对于每个查询,t 都会重置为 0。
2. 将路段号 x 上出现的交通拥堵周期替换为值 y(形式上,指定 ax = y)。
编写一段代码来有效处理上面给出的查询。
输入
第一行包含一个整数 n (1 ≤ n ≤ 105) — 连接 n + 1 个城市的高速公路路段数。
第二行包含 n 个整数 a1, a2, ..., an (2 ≤ ai ≤ 6) — 高速公路路段出现交通拥堵的周期。
下一行包含一个整数 q (1 ≤ q ≤ 105) — 要处理的查询数。
接下来的 q 行包含格式为 c, x, y 的查询描述(c — 查询类型)。
如果 c 是字符“A”,那么您的任务是处理第一种类型的查询。在这种情况下,满足以下约束:1 ≤ x < y ≤ n + 1。
如果c是字符“C”,那么您需要处理第二种类型的查询。在这种情况下,满足以下约束:1 ≤ x ≤ n,2 ≤ y ≤ 6。
输出
对于第一种类型的每个查询,输出一个整数——从城市 x 开车到城市 y 后时间 t 的最终值。按照输入中给出的顺序处理查询。
示例
输入 #1
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
输出 #1
5 3 14 6 2 4 4