Competitions

# Boring GCD

You are given an array a1, a2, a3, ..., an. There are 4 types of operations with it:

• l r x, for each i ∈ [l, r] replace ai with the value of x;
• 2 l r x, for each i ∈ [l, r] replace ai with the value of gcd(ai, x) function;
• 3 l r, output the value of maxai, lir;
• 4 l r, output the value of al + al+1 + ... + ar;

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

The first line contains two integers n, q (1n, m105) - the number of array elements and the number of queries.

The second line contains n positive integers a1, a2, ..., an - initial state of the array.

Next m lines contain the description of the queries, one per line. Queries are formatted the same way as in the problem statement above.

It is guaranteed that 1lrn and 1x109.

#### Output

For each 3-rd and 4-th query type output answer for this query in a separate line.

Time limit 2 seconds
Memory limit 128 MiB
Input example #1
5 11
1 6 8 7 3
3 1 5
4 1 5
2 1 5 6
3 1 5
4 2 4
1 1 5 10
3 1 4
4 3 5
2 3 4 3
3 2 3
4 4 5

Output example #1
8
25
6
9
10
30
10
11

Source 2019 Fall KBTU OPEN, Problem C