410057: GYM103934 E Fig trees of Hatshepsut

Memory Limit:256 MB Time Limit:4 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

E. Fig trees of Hatshepsuttime limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard 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).

ExampleInput
4 4
1 2 3 4
1 1 4
3 1 4
2 2 3 5
3 3 4
Output
6
7

Source/Category

加入题单

上一题 下一题 算法标签: