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