eolymp
bolt
Try our new interface for solving problems
Problems

Uzhland Union Bank

Uzhland Union Bank

Time limit 1 second
Memory limit 64 MiB

В базе старейшего ужляндского банка Uzhland Union Bank счета пронумерованы числами от 1 до N . На всех счетах открыта неограниченная кредитная линия (то есть сумма денег на счёте может быть и отрицательной). Используемая банковская система поддерживает три вида операций:

  1. l r c — прибавить к счетам с номерами l; l + 1; … ; r значение c.

  2. d c — прибавить к счетам с номерами d; 2 * d; 3 * d и так далее значение c.

  3. l r — узнать суммарное количество денег на счетах l; l + 1; … ; r. Требуется проэмулировать работу данной системы.

Input data

Первая строка входа содержит одно целое число 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).

Output data

На каждую операцию третьего типа выведите в выходной поток сумму денег на указанных счетах.

Examples

Input example #1
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
Output example #1
10
-6
15
20