Uzhland Union Bank
Uzhland Union Bank
В базе старейшего ужляндского банка Uzhland Union Bank счета пронумерованы числами от 1 до N . На всех счетах открыта неограниченная кредитная линия (то есть сумма денег на счёте может быть и отрицательной). Используемая банковская система поддерживает три вида операций:
l r c — прибавить к счетам с номерами l; l + 1; … ; r значение c.
d c — прибавить к счетам с номерами d; 2 * d; 3 * d и так далее значение c.
l r — узнать суммарное количество денег на счетах l; l + 1; … ; r. Требуется проэмулировать работу данной системы.
Входные данные
Первая строка входа содержит одно целое число N, (1 ≤ N ≤ 10^5
) — количество счетов. Во второй строке находятся N целых чисел a[1]
; a[2]
; … ; a[N]
(a[i]
≤ 10^9
) — начальное количество денег на каждом из счетов. В третьей строке находится целое число M, (1 ≤ M ≤ 10^5
) — количество операций. Следующие M строк задают сами операции. Первое число — это тип операции (одно целое число от 1 до 3).
Если тип операции равен 1, то за ним идут три целых числа l; r и c(1 ≤ l ≤ r ≤ N; c ≤ 10^4
).
Если тип операции равен 2, то за ним идут два целых числа d и c(1 ≤ d ≤ N; c ≤ 10^4
).
Если тип операции равен 3, то за ним идут два целых числа l и r(1 ≤ l ≤ r ≤ N).
Выходные данные
На каждую операцию третьего типа выведите в выходной поток сумму денег на указанных счетах.
Пример
10 1 2 3 4 5 6 -2 -3 -4 -5 9 3 4 8 1 7 10 2 3 7 10 2 2 -2 3 1 6 2 3 2 2 5 -7 1 2 8 4 3 3 10
10 -6 15 20