В базі старійшого ужляндського банку 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. Потрібно змоделювати роботу даної системи.

Вхідні дані

Перший рядок вхідних даних містить одне ціле число N, (1 ≤ N ≤ 105) — кількість рахунків. У другому рядку знаходиться N цілих чисел a1; a2; … ; aN(ai ≤ 109) — початкова кількість грошей на кожному рахунку. В третьому рядку знаходиться ціле число M, (1 ≤ M ≤ 105) — кількість операцій. Наступні M рядків задають самі операції. Перше число — це тип операції (одне ціле число від 1 до 3).

Якщо тип операції дорівнює 1, то за ним записано три цілих числа l; r і c(1 ≤ l ≤ r ≤ N; c ≤ 104).

Якщо тип операції дорівнює 2, то за ним записано два цілих числа d і c(1 ≤ d ≤ N; c ≤ 104).

Якщо тип операції дорівнює 3, то за ним записано два цілих числа l і r(1 ≤ l ≤ r ≤ N).

Вихідні дані

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