問題文

要素数 $N$ の数列 $A=\{a_1,a_2,...,a_N\}$ が与えられます。

以下の 4 種類のクエリが合計 $Q$ 個与えられるので、それらを順番に処理してください。

• $1lrx$

  • 各 $i\in [l,r]$ について、$a_i$ の値を $x$ で置き換える



• $2lrx$

  • 各 $i\in [l,r]$ について、$a_i$ の値を $gcd(a_i,x)$ で置き換える



• $3lr$

  • ${\displaystyle \underset{i\in [l,r]}{max}{a}_i}$ の値を出力する



• $4lr$

  • ${\displaystyle \sum _{i\in [l,r]}{a}_i}$ の値を出力する

入力

$NQ$
$a_1{a}_2\cdots a_N$
$quer{y}_1$
$quer{y}_2$
$\cdots$
$quer{y}_Q$

1 行目に数列の長さを表す整数 $N$ とクエリの数を表す整数 $Q$ がこの順で半角スペース区切りで与えられます。

2 行目には $N$ 個の整数が半角スペース区切りで与えられ、その内の $i$ 番目 $(1\le i\le N)$ の整数は、初期の $a_i$ の値を表します。

続く $Q$ 行のうちの $i$ 行目 $(1\le i\le Q)$ には、$i$ 番目のクエリが与えられます。

各クエリは

• $1lrx$

• $2lrx$

• $3lr$

• $4lr$

のいずれかの形式で与えられます。

入力は全部で $Q+2$ 行となり、以下の制約を満たします。

• 入力は全て整数
• $1\le N,Q\le {10}^5$
• $1\le a_i\le {10}^9(1\le i\le N)$
• クエリ1
  • $1\le l\le r\le N$
  • $1\le x\le {10}^9$
• クエリ2
  • $1\le l\le r\le N$
  • $1\le x\le {10}^9$
• クエリ3
  • $1\le l\le r\le N$
• クエリ4
  • $1\le l\le r\le N$
• クエリ3 と クエリ4 は合計 1 つ以上存在する

出力

各クエリ3に対して、${\displaystyle \underset{i\in [l,r]}{max}{a}_i}$ の値を、各クエリ4に対して、${\displaystyle \sum _{i\in [l,r]}{a}_i}$ の値を、それぞれ改行区切りで出力してください。

サンプル

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