Limits 1.5s, 512 MB

Congratulations! You’ve been hired in “Buggy Software Ltd.” And you’ve been already given your first assignment. Initially, you’ll be given a nn length array aa of numbers. Then you’ll be given qq queries of two types:

  1. 1 l r: meaning that calculate the sum of elements whose indices ii satisfy lirl \leq i \leq r
  2. 2 l r g: meaning that change all aia_i to aigcd(ai,g)\frac{a_i}{\gcd(a_i, g)}where lirl \leq i \leq r

You have to print the results of the queries of the first type.

Input

The first line will contain two integers nn and qq, the size of aa and number of queries respectively. The next line will contain nn space separated integers, the contents of array aa. Next qq lines will each contain the queries: 1 l r or 2 l r g.

1n21051 \leq n \leq 2\cdot 10^5

1q21051 \leq q \leq 2\cdot 10^5

1ai21051 \leq a_i \leq 2\cdot 10^5

1lrn1 \leq l \leq r \leq n

1g21051 \leq g \leq 2\cdot 10^5

Output

For each query of type 1, output the answer in a single line.

Sample

InputOutput
5 4
2 4 6 8 10
1 2 5
2 1 3 2
2 3 5 3
1 1 5
28
22

Submit

Login to submit.

Statistics

46% Solution Ratio
solaimanopeEarliest, Apr '21
user.2599Fastest, 0.2s
rkb_rdLightest, 49 MB
fahimcp495Shortest, 1503B
Toph uses cookies. By continuing you agree to our Cookie Policy.