GCD and Sum

upobir Criterion 2021 Round 12
Limits 1.5s, 512 MB

Congratulations! You’ve been hired in “Buggy Softwares 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. 11 ll rr : meaning that calculate the sum of elements whose indices ii satisfy lirl \leq i \leq r
  2. 22 ll rr gg : 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: 11 ll rr or 22 ll rr gg.

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 11, 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

39% Solution Ratio
solaimanopeEarliest, Apr '21
upobirFastest, 0.3s
BigBagLightest, 53 MB
mahade31Shortest, 1534B
Toph uses cookies. By continuing you agree to our Cookie Policy.