eolymp
Competitions

2019 Fall KBTU OPEN

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