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).
Выходные данные
На каждую операцию третьего типа выведите в выходной поток сумму денег на указанных счетах.