F. Meltdown
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Climate change is real, and polar bears are losing their habitats, causing them to migrate.

In the North Pole there are $$$N$$$ pillars of ice, standing in a line. As temperatures rise, some of the pillars of ice will start to melt. Now, time works differently at the North Pole, and the length of each day is $$$Q$$$ minutes.

In each of the $$$Q$$$ minutes, something will happen. During some minutes, the $$$l$$$th pillar, the $$$r$$$th pillar, and every pillar in between will shrink to $$$\lfloor {\frac{1}{x}} \rfloor$$$ of its height. In case no pillars melt in a given minute, a pizzly bear (grizzly polar bear abomination) will take the opportunity to ask you: what is the sum of the heights of the pillars in an interval?

Answer all of the pizzly bear's questions so it won't eat you.

Also, in case the new height of a pillar is a decimal, the pillar will continue melting until its height is an integer. So, there will never be any pillars with non-integer heights.

Input

Line $$$1$$$: An integer $$$N$$$ ($$$1 \le N \le 10^5$$$) representing the number of pillars.

Line $$$2$$$: $$$N$$$ space separated integers $$$a_i$$$, each specifying the height of the $$$i$$$th ice pillar.

Line $$$3$$$: $$$Q$$$ ($$$1 \le Q \le 10^5$$$), the number of minutes in a day

Line $$$4...Q+3$$$: Queries, either of the type $$$1$$$ $$$l$$$ $$$r$$$ $$$x$$$ or $$$2$$$ $$$l$$$ $$$r$$$. ($$$1 \le l, r \le N$$$; $$$1 \le x \le 10^9$$$). Queries starting in $$$1$$$ signify an "ice melt" event, while queries starting in $$$2$$$ signify a "pillar height sum" event.

Output

For each query of type $$$2$$$, print the answer on its own separate line.

Example
Input
5
2 2 4 3 5
3
2 1 3
1 1 4 2
2 1 3
Output
8
4