Uzhland Union Bank#8273
In the database of the senior Uzhland bank, Uzhland Union Bank, accounts are numbered from to . Each account allows an unlimited credit line, which means the account balance can be negative. The banking system supports three types of operations:
— Add the value to each account numbered from to .
— Add the value to each account with numbers , , , and so on (all positive multiples of not exceeding ).
— Calculate the total balance of accounts from to (inclusive).
Your task is to simulate the system and perform the given operations.
The first line contains a single integer (1 \le N \le 10^5) — the number of accounts.
The second line contains integers a_1, a_2, \ldots, a_N (|a_i| \le 10^9), the initial balances of the accounts.
The third line contains a single integer (1 \le M \le 10^5) — the number of operations.
The following lines describe the operations. The first number in each line is the operation type (an integer from to ):
If the operation type is , the line then contains three integers , , and (1 \le l \le r \le N;\ |c| \le 10^4).
If the operation type is , the line then contains two integers and (1 \le d \le N;\ |c| \le 10^4).
If the operation type is , the line then contains two integers and (1 \le l \le r \le N).
For each operation of the third type, output the sum of the balances in the specified range of accounts on a separate line.
Example 1