Uzhland Union Bank
In the database of the senior Uzhland bank, Uzhland Union Bank, accounts are numbered from 1 to N. Each account has an unlimited credit line, meaning the balance can be negative. The banking system supports three types of operations:
l r c — Add the value c to each account numbered from l to r.
d c — Add the value c to accounts numbered d, 2 * d, 3 * d, and so on.
l r — Calculate the total balance of accounts from l to r. Your task is to simulate these operations.
Input Data
The first line contains a single integer N (1 ≤ N ≤ 10^5), representing the number of accounts. The second line contains N integers a[1], a[2], ..., a[N] (a[i] ≤ 10^9), which are the initial balances of each account. The third line contains an integer M (1 ≤ M ≤ 10^5), indicating the number of operations. The following M lines describe the operations. The first number on each line indicates the type of operation (an integer from 1 to 3).
For an operation of type 1, the line is followed by three integers l, r, and c (1 ≤ l ≤ r ≤ N; c ≤ 10^4).
For an operation of type 2, the line is followed by two integers d and c (1 ≤ d ≤ N; c ≤ 10^4).
For an operation of type 3, the line is followed by two integers l and r (1 ≤ l ≤ r ≤ N).
Output Data
For each operation of the third type, output the sum of the balances in the specified range of accounts.