题目描述

一些国家由 $n+1$ 个城市组成，这些城市位于一个笔直的路上，我们把按照他们在路上的顺序把这些城市编号为 $1\sim n+1$。这样，第 $i$ 个线段连接着第 $i$ 和第 $i+1$ 个城市。每一个城市有一个拥堵值 $a[i]$，如果当前时间能被 $a[i]$ 整除，那么通过这条公路需要两分钟，否则需要一分钟。

给出每条公路的 $a[i]$，以及 $m$ 次操作，操作有两种：

1. C x d：把第 $x$ 条路的拥堵时刻改成 $d$。
2. A x y：问 $x$ 到 $y$ 城市所需要的时间。

输入格式

第一行一个整数 $n$，$1\le n\le 10^{5}$。

第二行 $n$ 个整数 $a_i$，$2\le a_{i}\le 6$。

第三行一个整数 $m$，$1\le q\le 10^{5}$。

接下来 $q$ 行，每行一个操作，对于修改操作，$2 \le d \le 6$。

输出格式

对于每个询问，在一行中输出一个整数表示答案。

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

5
3
14
6
2
4
4