# 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 $n$ length array $a$ of numbers. Then you’ll be given $q$ queries of two types:

1. $1$ $l$ $r$ : meaning that calculate the sum of elements whose indices $i$ satisfy $l \leq i \leq r$
2. $2$ $l$ $r$ $g$ : meaning that change all $a_i$ to $\frac{a_i}{\gcd(a_i, g)}$where $l \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 $n$ and $q$ , the size of $a$ and number of queries respectively. The next line will contain $n$ space separated integers, the contents of array $a$. Next $q$ lines will each contain the queries: $1$ $l$ $r$ or $2$ $l$ $r$ $g$.

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

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

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

$1 \leq l \leq r \leq n$

$1 \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


### Statistics

39% Solution Ratio

solaimanopeEarliest, 3M ago

upobirFastest, 0.3s

BigBagLightest, 53 MB

mahade31Shortest, 1534B

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

 Criterion 2021 Round 12Ended 3M ago