Description

During several decades, scientists from planet Nibiru are working to create an engine that would allow spacecrafts to fall into hyperspace and move there with superluminal velocity. To check whether their understanding of PRoperties of hyperspace is right, scientists have developed the following experiment.

A chain of n particles is placed in hyperspace. Positions of particles in the chain are numbered from 1 to n. Initially, *i*th particle has charge ai$a_i$.

According to the current theory, if particle number i got special radiation with power d, oscillations would spread by hyperspace and increase by d charge of particles with numbers i, 2*i*, 3*i* and so on (i.e. with numbers divisible by i).

Using a special device, scientists can direct the radiation of the same power at a segment of adjacent particles. For example, suppose that initially there were 6 particles with zero charges, and scientists have sent radiation with power five to particles with numbers 2 and 3. Then charge of 2nd, 3rd, and 4th particles will increase to five, and charge of 6th particle will increase to ten (the oscillations will reach it twice). Charge of other particles won’t change.

Charge of particles can’t change without impact of the device.

During the experiment, the scientists plan to perform actions of the following types:

Your program will be given a list of performed actions. For every action of the first type the program should output value of expected charge of the particle calculated in accordance with the current theory described above.

If the expected charges of the particles coincide with charges measured during the experiment, it will turn out that scientists’ understanding of hyperspace is right, and they will be able to start building of the hyperdrives. Then inhabitants of Nibiru will finally meet their brothers from Earth in just a few years!

Input

The first line contains a single integer n — number of particles (1≤n≤3×105$1/le n /le 3/times 10^5$).

The second line contains n integers a**i separated by spaces — initial charges of the particles (0≤ai≤106$0/le a_i/le 10^6$).

The third line contains a single integer q — number of actions in the experiment (1≤q≤3×105$1/le q/le 3/times 10^5$).

Each of the following q lines contain two or four integers — a description of the next action in one of the following formats:

Output

For each query output the expected charge of the *i*th particle.

題意

給定 n 個數，每個數均有一個初值 a1,a2,...,an$a_1, a_2, ..., a_n$。之后有 q 個操作。操作分為兩種：

分析

很顯然，初始值不會對后續的操作產生任何影響，此處僅需要單獨保存在一個數組中，在每次詢問的最后加上初值就可以。

考慮到區間更新，單點查詢的話，很容易能夠想到套用樹狀數組的板。

但是，此處的區間更新顯示不只是更新區間，區間內的點同時也會對其倍數點產生影響。如果考慮在更新的同時更新后續倍數點，復雜度顯然無法滿足條件。因此，對于2 l r d ，僅考慮更新區間 [l, r] 。單次操作復雜度為 O(logN)$O(logN)$

由于上述無法處理區間更新帶來的后續倍數點的更新，故在單點查詢過程中必須對最后結果加以保證。我想到的方法是——每個點的更新對其倍數點產生影響，可以理解為每個點的值必須考慮其約數點對其的影響，故暴力尋找點的約數，并通過單點查詢獲取對當前值的貢獻。單次操作復雜度O(logN×N??√)$O(logN/times /sqrt{N})$

雖然覺得這個代碼是不可能過的，但是，抱著試一試的態度，果斷Accepted 。

代碼