E. Fig trees of Hatshepsut
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

One of pharaoh Hatshepsut's greatest pride was her gardens. Right next to her palace there was a beautiful sequence of fig trees. The trees are numbered from $$$1$$$ to $$$n$$$ and the $$$i$$$-th tree has $$$a_i$$$ figs.

Fig trees are very peculiar, and react in an interesting way when they are shaken. If someone shakes a fig tree with $$$x$$$ figs, after this $$$\phi(x)$$$ figs remain, where $$$\phi(x)$$$ counts the positive integers up to $$$x$$$ that is relatively prime to $$$x$$$. Following is the value of $$$\phi$$$ for integers from 1 to 10 is $$$\{1,1,2,2,4,2,6,4,6,4\}$$$.

The pharaoh is constantly dissatisfied with her fig garden and demands her servants to do some changes to it. In total, she may demand three types of operations

  • 1 L R: for $$$i$$$ from $$$L$$$ to $$$R$$$ (inclusive) shake the $$$i$$$-th fig tree (changing $$$a_i$$$ to $$$\phi(a_i)$$$).
  • 2 L R x: for $$$i$$$ from $$$L$$$ to $$$R$$$ (inclusive) change the $$$i$$$-th fig tree to one with $$$x$$$ figs (changing $$$a_i$$$ to $$$x$$$).
  • 3 L R: print the sum of $$$a_i$$$ for $$$i$$$ from $$$L$$$ to $$$R$$$ (inclusive).

The great gardener of Hatshepsut gets lost with so many orders! She asks for your help, given a list of Hatshepsut's orders print the answer for every order of type 3.

Input

The first line consists of 2 integers $$$n$$$ and $$$q$$$ ($$$1 \leq n , q \leq 2 \cdot 10^5$$$). The next line consists of $$$n$$$ integers $$$a_i$$$ ($$$1 \leq a_i \leq 1 \cdot 10^6$$$). Then follow $$$q$$$ lines, each consisting of one operation. The first number $$$t$$$ is the type of the operation ($$$1 \leq t \leq 3$$$), then follow two integers $$$L$$$ and $$$R$$$ ($$$1 \leq L \leq R \leq n$$$) and if $$$t$$$ equals to $$$2$$$ the forth and last integer is $$$x$$$ ($$$1 \leq x \leq 1 \cdot 10^6$$$).

Output

For each operation of type 3, print one line with one integer, the sum of $$$a_i$$$ for $$$i$$$ from $$$L$$$ to $$$R$$$ (inclusive).

Example
Input
4 4
1 2 3 4
1 1 4
3 1 4
2 2 3 5
3 3 4
Output
6
7