# 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 $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 ### Submit 