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

Придворный волшебник Зигзаг хочет прославиться как великий математик. Для этого ему нужна своя теорема, как у Коши, или своя сумма, как у Минковского. Но больше всего ему хочется иметь свою последовательность, как у Фибоначчи, и свою функцию, как у Эйлера.

Последовательностью Зигзага с коэффициентом зигзаговости 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.

  1. Операция присвоения. Параметры операции: (p, v). Операция обозначает присвоение p-му элементу массива значения v. После применения операции значение элемента ap массива равно v.
  2. Операция Зигзага. Параметры операции: (l, r, z). Операция обозначает вычисление функции Зигзага Z(l, r, z).

Познайте магическую силу зигзагов, реализуйте описанные операции.

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

В первой строке записано целое число n (1 ≤ n ≤ 105) — количество элементов в массиве a. Во второй строке через пробел записаны n целых чисел: a1, a2, ..., an (1 ≤ ai ≤ 109) — элементы массива.

В третьей строке записано целое число m (1 ≤ m ≤ 105) — количество операций. В следующих m строках записаны описания операций. Описание операции начинается с целого числа ti (1 ≤ ti ≤ 2) — типа операции.

  • Если ti = 1 (операция присвоения), то далее в строке через пробел записаны два целых числа: pi, vi (1 ≤ pi ≤ n; 1 ≤ vi ≤ 109) — параметры операции присвоения.
  • Если ti = 2 (операция Зигзага), то далее в строке через пробел записаны три целых числа: li, ri, zi (1 ≤ li ≤ ri ≤ n; 2 ≤ zi ≤ 6) — параметры операции Зигзага.

Операции необходимо выполнять в том порядке, в котором они заданы во входных данных.

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

Для каждой операции Зигзага выведите вычисленное значение функции Зигзага в отдельной строке. Значения для операций Зигзага выводите в том порядке, в котором эти операции заданы во входных данных.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Примеры
Входные данные
5
2 3 1 5 5
4
2 2 3 2
2 1 5 3
1 3 5
2 1 5 3
Выходные данные
5
26
38
Примечание

Пояснение к примеру:

  • Результат первой операции Z(2, 3, 2) = 3·1 + 1·2 = 5.
  • Результат второй операции Z(1, 5, 3) = 2·1 + 3·2 + 1·3 + 5·2 + 5·1 = 26.
  • После выполнения третьей операции массив a равен: 2, 3, 5, 5, 5.
  • Результат четвертой операции Z(1, 5, 3) = 2·1 + 3·2 + 5·3 + 5·2 + 5·1 = 38.