SOLVE

LATER

Greatest common divisor

/

You are given array * A*. There are

, for each*1 l r x**i ∈ [l, r]*replacewith the value of*a*_{i}.**x**, for each**2 l r x***i ∈ [l, r]*replacewith the value of the**a**_{i}function.*gcd(a*_{i}, x), print the value of*3 l r*.**max a**_{i}, l ≤ i ≤ r, print the value of**4 l r**.*a*_{l}+ a_{l+1}+ ... + a_{r}

A greatest common divisor (**gcd(a, b)**) of two positive integers **a** and **b** is equal to the biggest integer **d** such that both integers **a** and **b** are divisible by **d**.

**Input format**

- The first line contains two integers
- the number of array elements and the number of queries.*n, m (1 ≤ n, m ≤ 10*^{5}) - The second line contains
positive integers*n*- initial state of the array.(**a**_{1}, a_{2}, ..., a_{n})**1 ≤ max A**_{i }≤ 10^{9}, 1 ≤ i ≤ n - Next
lines contain the description of the queries, one per line. Queries are formatted the same way as in the problem statement above.*m* - It is guaranteed that
and**1 ≤ l ≤ r ≤ n**.*1 ≤ x ≤ 10*^{9}

**Output format**

For each third and fourth query type, print the answer for this query in a separate line.

Explanation

Array before queries is [10,12,6,8]

Answer for queries 3 1 4 = 12, because max(10,12,6,8) = 12

Answer for queries 4 1 4 = 36, because 10 + 12 + 6 + 8 = 36

After queries-update 2 2 4 4 array is [10, 4, 2, 4]

Answer for queries 3 2 4 = 4, because max(4,2,4) = 4

After queries-update 1 1 4 2 array is [2, 2, 2, 2]

Answer for queries 4 1 4 = 36, because 2 + 2 + 2 + 2 = 8

Time Limit:
1.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Initializing Code Editor...