Uzhland Union Bank#8273

Uzhland Union Bank

1 секунда

64 мегабайти

Легка

У базі найстарішого ужлянського банку Uzhland Union Bank рахунки пронумеровані числами від $1$ до $N$ . На кожному рахунку відкрита необмежена кредитна лінія, тобто баланс може бути від'ємним. Банківська система підтримує три типи операцій:

$l$ $r$ $c$ — додати значення $c$ до кожного рахунку з номерами від $l$ до $r$ .
$d$ $c$ — додати значення $c$ до кожного рахунку з номерами $d$ , $2 d$ , $3 d$ і так далі (всі позитивні кратні $d$ , що не перевищують $N$ ).
$l$ $r$ — обчислити загальний баланс рахунків з номерами від $l$ до $r$ (включно).

Потрібно змоделювати роботу цієї системи та виконати всі задані операції.

Вхідні дані

У першому рядку записано одне ціле число $N$ ( $1 \leq N \leq 1 0^{5}$ 1 \le N \le 10^5) — кількість рахунків.

У другому рядку йдуть $N$ цілих чисел $a_{1}, a_{2}, \dots, a_{N}$ a_1, a_2, \ldots, a_N ( $∣ a_{i} ∣ \leq 1 0^{9}$ |a_i| \le 10^9) — початкові баланси рахунків.

У третьому рядку міститься одне ціле число $M$ ( $1 \leq M \leq 1 0^{5}$ 1 \le M \le 10^5) — кількість операцій.

Наступні $M$ рядків описують самі операції. Перше число кожного рядка — це тип операції (ціле число від $1$ до $3$ ):

Якщо тип операції $1$ , далі йдуть три цілі числа $l$ , $r$ і $c$ ( $1 \leq l \leq r \leq N; ∣ c ∣ \leq 1 0^{4}$ 1 \le l \le r \le N;\ |c| \le 10^4).
Якщо тип операції $2$ , далі йдуть два цілі числа $d$ та $c$ ( $1 \leq d \leq N; ∣ c ∣ \leq 1 0^{4}$ 1 \le d \le N;\ |c| \le 10^4).
Якщо тип операції $3$ , далі йдуть два цілі числа $l$ і $r$ ( $1 \leq l \leq r \leq N$ 1 \le l \le r \le N).

Вихідні дані

Для кожної операції третього типу виведіть суму балансів вказаних рахунків у окремому рядку.

Приклади

Приклад 1