Problem: At the children's day, the child came to Picks's house, and messed his house up. Picks was angry at him. A lot of important things were lost, in particular the favorite sequence of Picks.

Fortunately, Picks remembers how to repair the sequence. Initially he should create an integer array a[1], a[2], ..., a[n]. Then he should perform a sequence of m operations. An operation can be one of the following:

  1. Print operation l, r. Picks should write down the value of <image>. 
  2. Modulo operation l, r, x. Picks should perform assignment a[i] = a[i] mod x for each i (l ≤ i ≤ r). 
  3. Set operation k, x. Picks should set the value of a[k] to x (in other words perform an assignment a[k] = x). 



Can you help Picks to perform the whole sequence of operations?

Input

The first line of input contains two integer: n, m (1 ≤ n, m ≤ 105). The second line contains n integers, separated by space: a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ 109) — initial value of array elements.

Each of the next m lines begins with a number type <image>. 

  * If type = 1, there will be two integers more in the line: l, r (1 ≤ l ≤ r ≤ n), which correspond the operation 1. 
  * If type = 2, there will be three integers more in the line: l, r, x (1 ≤ l ≤ r ≤ n; 1 ≤ x ≤ 109), which correspond the operation 2. 
  * If type = 3, there will be two integers more in the line: k, x (1 ≤ k ≤ n; 1 ≤ x ≤ 109), which correspond the operation 3. 

Output

For each operation 1, please print a line containing the answer. Notice that the answer may exceed the 32-bit integer.

Examples

Input

5 5
1 2 3 4 5
2 3 5 4
3 3 5
1 2 5
2 1 3 3
1 1 3


Output

8
5


Input

10 10
6 9 6 7 6 1 10 10 9 5
1 3 9
2 7 10 9
2 5 10 8
1 4 7
3 3 7
2 7 9 9
1 2 4
1 6 6
1 5 9
3 1 10


Output

49
15
23
1
9

Note

Consider the first testcase:

  * At first, a = {1, 2, 3, 4, 5}. 
  * After operation 1, a = {1, 2, 3, 0, 1}. 
  * After operation 2, a = {1, 2, 5, 0, 1}. 
  * At operation 3, 2 + 5 + 0 + 1 = 8. 
  * After operation 4, a = {1, 2, 2, 0, 1}. 
  * At operation 5, 1 + 2 + 2 = 5. 

Solution (in JAVA):

Solution:
import static java.lang.Math.*;
import static java.lang.System.currentTimeMillis;
import static java.lang.System.exit;
import static java.lang.System.arraycopy;
import static java.util.Arrays.sort;
import static java.util.Arrays.binarySearch;
import static java.util.Arrays.fill;

import java.util.*;
import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {
        try {
            if (new File("input.txt").exists())
                System.setIn(new FileInputStream("input.txt"));
        } catch (SecurityException e) {
        }
        new Thread(null,new Runnable() {
            
            public void run() {
                try {
                    new Main().run();
                } catch (IOException e) {
                    // TODO Auto-generated catch block
                    e.printStackTrace();
                }
            }
        },"1", 1 << 20).run();
    }

    BufferedReader in;
    PrintWriter out;
    StringTokenizer st = new StringTokenizer("");

    private void run() throws IOException {
        in = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        solve();
        in.close();
        out.close();
    }
    
    final int INF = Integer.MAX_VALUE/2;
    class RMQ{
        int[] t;
        int[] indexMax;
        int n, treeSize;
        public RMQ(int[] a){
            n = 0;
            while((1 << n) < a.length)
                n++;
            treeSize = 1 << n;
            n++;
            n = 1 << n;
            t = new int[n];
            indexMax = new int[n];
            fill(indexMax, -1);
            fill(t, -INF);
            for(int i = 0; i < a.length; i++){
                t[i+n/2] = a[i];
                indexMax[i+n/2] = i;
            }
            for(int i = n/2 - 1; i > 0; i--){
                if(t[2 * i] > t[2 * i + 1]){
                    t[i] = t[2 * i];
                    indexMax[i] = indexMax[2 * i];
                } else {
                    t[i] = t[2 * i + 1];
                    indexMax[i] = indexMax[2 * i + 1];
                }
            }
        }
        
        int[] max(int l, int r){
            return max(1, 0, treeSize-1, l,r);
        }
        int[] max(int v, int l, int r, int ll, int rr){
            if(ll > rr)
                return new int[] {-INF, -1};
            if(l == ll && r == rr)
                return new int[] {t[v], indexMax[v]};
            int m = (l + r) >> 1;
            int[] left = max(v * 2, l, m, ll, java.lang.Math.min(rr,m));
            int[] right = max(v * 2 + 1,m+1,r,java.lang.Math.max(m+1, ll), rr);
            if(left[0] > right[0])
                return left;
            else
                return right;
        }
        void change(int index, int newValue){
            change(1, 0, treeSize-1, index, newValue);
        }
        void change(int v, int l, int r, int index, int newValue){
            if(l == r)
                t[v] = newValue;
            else{
                int m = (l+r) >> 1;
                if(index <= m)
                    change(v * 2, l, m, index, newValue);
                else
                    change(v * 2 + 1, m+1, r, index, newValue);
                if(t[2 * v] > t[2 * v + 1]){
                    t[v] = t[2 * v];
                    indexMax[v] = indexMax[2 * v];
                } else {
                    t[v] = t[2 * v + 1];
                    indexMax[v] = indexMax[2 * v + 1];
                }
            }
        }
    }
    class RSQ{
        long[] t;
        int n, treeSize;
        public RSQ(int[] a){
            n = 0;
            while((1 << n) < a.length)
                n++;
            treeSize = 1 << n;
            n++;
            n = 1 << n;
            t = new long[n];
            fill(t, 0);
            for(int i = 0; i < a.length; i++)
                t[i+n/2] = a[i];
            for(int i = n/2 - 1; i > 0; i--)
                t[i] = t[2 * i] + t[2 * i + 1];
        }
        long sum(int l,int r){
            return sum(1, 0, treeSize-1, l, r);
        }
        long sum(int v, int l, int r, int ll, int rr){
            if(ll > rr)
                return 0;
            if(l == ll && r == rr)
                return t[v];
            int m = (l + r) >> 1;
            return sum(2 * v, l, m, ll, min(rr, m)) + sum(2 * v + 1, m+1, r, max(m+1, ll), rr);
        }
        void change(int index, int newValue){
            change(1, 0, treeSize-1, index, newValue);
        }
        void change(int v, int l, int r, int index, int newValue){
            if(l == r)
                t[v] = newValue;
            else{
                int m = (l+r) >> 1;
                if(index <= m)
                    change(v * 2, l, m, index, newValue);
                else
                    change(v * 2 + 1, m+1, r, index, newValue);
                t[v] = t[2*v] + t[2 * v + 1];
            }
        }
        public String toString(){
            String s = "";
            for(int i = 0; i < treeSize; i++){
                s += t[i + n/2] + ",";
            }
            return s;
        }
    }

    private void solve() throws IOException {
//      RMQ rmq = new RMQ(new int[] {1,2,3,4,5,6});
//      System.err.println(rmq.max(3,3)[0]);
        
        int n = nextInt(), m = nextInt();
        int[] a = new int[n];
        for(int i = 0; i < n; i++)
            a[i] = nextInt();
        RMQ rmq = new RMQ(a);
        RSQ rsq = new RSQ(a);
        for(int i = 0; i < m; i++){
            int type = nextInt();
            if(type == 1){
                int l = nextInt()-1, r = nextInt()-1;
                out.println(rsq.sum(l, r));
            } else if(type == 2){
                int l = nextInt()-1, r = nextInt()-1, x = nextInt();
                int maxVal = rmq.max(l, r)[0], indexMaxVal = rmq.max(l, r)[1];
                while(maxVal >= x){
                    rmq.change(indexMaxVal, maxVal % x);
                    rsq.change(indexMaxVal, maxVal % x);
                    maxVal = rmq.max(l, r)[0];
//                  System.err.println(maxVal + " "  + x + " " + indexMaxVal);
//                  System.err.println(rsq.toString());
                    indexMaxVal = rmq.max(l, r)[1];
                }
            } else {
                int k = nextInt()-1, x = nextInt();
                rsq.change(k, x);
                rmq.change(k, x);
            }
        }
    }
    
    int gcd(int a, int b){return b == 0 ? a : gcd(b,a%b);}
    
    String arrayToString(int[] m){
        return Arrays.toString(m);
    }
    
    String nextToken() throws IOException {
        while (!st.hasMoreTokens())
            st = new StringTokenizer(in.readLine());
        return st.nextToken();
    }
    int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }
    long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }
    double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }
    String nextLine() throws IOException {
        st = new StringTokenizer("");
        return in.readLine();
    }
    boolean EOF() throws IOException {
        while (!st.hasMoreTokens()) {
            String s = in.readLine();
            if (s == null)
                return true;
            st = new StringTokenizer(s);
        }
        return false;
    }
}