Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

GCD and Sum

By upobir · 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

Discussion

Statistics


39% Solution Ratio

solaimanopeEarliest, 3M ago

upobirFastest, 0.3s

BigBagLightest, 53 MB

mahade31Shortest, 1534B

Submit

Login to submit

Editorial

Use sieve to keep track of prime factorization of numbers 111 to 2⋅1052 \cdot 10^52⋅105 . Then for a...

Related Contests