D. Why Does Every Baozii Cup Have a GCD Problem
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of length $$$n$$$. Your task is to process $$$q$$$ queries of three types:

  • $$$1~i~x$$$ — set $$$a_i:=x$$$.
  • $$$2~l~r~x$$$ — for each $$$i$$$ such that $$$l \le i \le r$$$, set $$$a_i:=\gcd(a_i,x)$$$, where $$$\gcd(x,y)$$$ represents the largest integer that divides both $$$x$$$ and $$$y$$$.
  • $$$3~l~r$$$ — compute $$$\sum_{i=l}^ra_i$$$.

Output the answer for each type $$$3$$$ query.

Input

The first line of each test contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le q \le 2 \cdot 10^5$$$) — the length of $$$a$$$ and the number of queries, respectively.

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 10^7$$$) — the elements of $$$a$$$.

Each of the next $$$q$$$ lines contains a query in one of three formats:

  • $$$1~i~x$$$ ($$$1 \le i \le n$$$, $$$1 \le x \le 10^7$$$) — set $$$a_i:=x$$$.
  • $$$2~l~r~x$$$ ($$$1 \le l \le r \le n$$$, $$$1 \le x \le 10^7$$$) — set $$$a_i:=\gcd(a_i,x)$$$ for each $$$l \le i \le r$$$.
  • $$$3~l~r$$$ ($$$1 \le l \le r \le n$$$) — compute $$$\sum_{i=l}^ra_i$$$.

It is guaranteed that there is at least one type $$$3$$$ query.

Output

For each type $$$3$$$ query, output the answer — the sum of $$$a_l,a_{l+1},\ldots,a_r$$$.

Example
Input
5 10
1 2 3 4 5
3 1 5
1 1 10
3 1 5
2 1 4 2
3 1 4
1 3 15
2 3 5 5
3 1 5
2 1 5 1
3 2 4
Output
15
24
7
15
3