You are given array A. There are 4 types of operations associated with it:

• 1 l r x, for each i ∈ [l, r] replace a_i with the value of x.
• 2 l r x, for each i ∈ [l, r] replace a_i with the value of the gcd(a_i, x) function.
• 3 l r, print the value of max a_i, l ≤ i ≤ r.
• 4 l r, print the value of 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 n, m (1 ≤ n, m ≤ 10⁵) - the number of array elements and the number of queries.
• The second line contains n positive integers a₁, a₂, ..., a_n - initial state of the array.(1 ≤ max A_i ≤ 10⁹, 1 ≤ i ≤ n)
• 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 1 ≤ l ≤ r ≤ n and 1 ≤ x ≤ 10⁹.

Output format

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