Некоторая страна состоит из (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 запросов двух видов:
- определить конечное значение времени t после поездки из города x в город y (x < y) при использовании описанной выше тактики. Обратите внимание, что перед каждым подобным запросом t устанавливается равным нулю;
- изменить период появления пробок на участке с номером x на значение y (формально, выполнить присвоение ax = y).
Напишите программу, которая будет эффективно обрабатывать описанные выше запросы.
Выходные данные
На каждый запрос первого типа выведите одно число — конечное значение времени t после поездки из города x в город y. Запросы необходимо обрабатывать в том порядке, в котором они заданы во входных данных.
Примеры
| № | Входные данные | Выходные данные |
|
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
|
5
3
14
6
2
4
4
|