Придворный волшебник Зигзаг хочет прославиться как великий математик. Для этого ему нужна своя теорема, как у Коши, или своя сумма, как у Минковского. Но больше всего ему хочется иметь свою последовательность, как у Фибоначчи, и свою функцию, как у Эйлера.
Последовательностью Зигзага с коэффициентом зигзаговости z будем называть бесконечную последовательность Siz (i ≥ 1; z ≥ 2), которая определяется следующим образом:
- Siz = 2, при
; -
, при 
; -
, при 
.
Операция 
обозначает взятие остатка от деления числа x на число y. Например, начало последовательности Si3 (зигзаговости 3) выглядит так: 1, 2, 3, 2, 1, 2, 3, 2, 1.
Пусть задан массив a, состоящий из n целых чисел. Обозначим элемент номер i (1 ≤ i ≤ n) массива за ai. Функцией Зигзага будем называть функцию: 
, где l, r, z удовлетворяют неравенствам 1 ≤ l ≤ r ≤ n, z ≥ 2.
Чтобы лучше познакомиться с последовательностью и функцией Зигзага, волшебник Зигзаг предлагает Вам реализовать следующие операции над заданным массивом a.
- Операция присвоения. Параметры операции: (p, v). Операция обозначает присвоение p-му элементу массива значения v. После применения операции значение элемента ap массива равно v.
- Операция Зигзага. Параметры операции: (l, r, z). Операция обозначает вычисление функции Зигзага Z(l, r, z).
Познайте магическую силу зигзагов, реализуйте описанные операции.
Выходные данные
Для каждой операции Зигзага выведите вычисленное значение функции Зигзага в отдельной строке. Значения для операций Зигзага выводите в том порядке, в котором эти операции заданы во входных данных.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.