D. Пробки в стране
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Некоторая страна состоит из (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. определить конечное значение времени t после поездки из города x в город y (x < y) при использовании описанной выше тактики. Обратите внимание, что перед каждым подобным запросом t устанавливается равным нулю;
  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.

Выходные данные

На каждый запрос первого типа выведите одно число — конечное значение времени t после поездки из города x в город y. Запросы необходимо обрабатывать в том порядке, в котором они заданы во входных данных.

Примеры
Входные данные
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