Problem Statement

You are given a sequence $A = \{ a_1, a_2, ... , a_N \} \ $ with $N$ elements.

A total of $Q$ queries of the following 4 types are given. Process them in order.

• $1 \ l \ r \ x$

  • For each $i \in [l, r]$, replace the value of $a_i$ with $x$.



• $2 \ l \ r \ x$

  • For each $i \in [l, r]$, replace the value of $a_i$ with $gcd(a_i, x)$.



• $3 \ l \ r$

  • Output the value of $\displaystyle \max_{i \in [l, r]} a_i $.



• $4 \ l \ r$

  • Output the value of $\displaystyle \sum_{i \in [l, r]} a_i $.

Input

$N \ Q$
$a_1 \ a_2 \ \cdots \ a_N$
$query_1$
$query_2$
$\cdots$
$query_Q$

The first line contains an integer $N$ representing the length of the sequence and an integer $Q$ representing the number of queries, in this order, separated by a space.

The second line contains $N$ integers separated by spaces, where the $i$-th integer $(1 \le i \le N)$ represents the initial value of $a_i$.

The $i$-th $(1 \le i \le Q)$ of the following $Q$ lines contains the $i$-th query.

Each query is given in one of the following formats:

• $1 \ l \ r \ x$

• $2 \ l \ r \ x$

• $3 \ l \ r$

• $4 \ l \ r$

(each query takes one of the formats above).

The input consists of $Q + 2$ lines in total and satisfies the following constraints.

• All input values are integers.
• $1 \le N, Q \le 10^5$
• $1 \le a_i \le 10^9 \ \ (1 \le i \le N)$
• Query 1
  • $1 \le l \le r \le N$
  • $1 \le x \le 10^9$
• Query 2
  • $1 \le l \le r \le N$
  • $1 \le x \le 10^9$
• Query 3
  • $1 \le l \le r \le N$
• Query 4
  • $1 \le l \le r \le N$
• There is at least one query of type 3 or type 4 in total.

Output

For each query 3, output the value of $ \displaystyle \max_{i \in [l, r]} a_i $, and for each query 4, output the value of $ \displaystyle \sum_{i \in [l, r]} a_i $, separated by newlines.

Sample

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

8
25
6
9
10
30
10
11