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 java.io.FileInputStream;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.*;
import static java.lang.Math.*;

public class Main {
    private static boolean oj = System.getProperty("ONLINE_JUDGE") != null;
    private static InputReader in;
    private static PrintWriter out;
    ////////////////////////////////////////////////////////////////////////////////////////////////////
    private static int min(int... a){int min=a[0]; for(int i:a) min=Math.min(min, i); return min;}
    private static int max(int... a){int max=a[0]; for(int i:a) max=Math.max(max, i); return max;}
    private static long min(long... a){long min=a[0]; for(long i:a)min=Math.min(min, i); return min;}
    private static long max(long... a){long max=a[0]; for(long i:a)max=Math.max(max, i); return max;}
    private static String strm(String str, long m) {
        String ans = "";
        while(m > 0) {
            if ((m&1) == 1) ans = ans.concat(str);
            str = str.concat(str); m >>= 1;
        } return ans;
    }
    private static long mod(long a, long mod) {long res = a%mod; return res>=0 ? res : res+mod;}
    private static int mod(int a, int mod) {int res = a%mod; return res>=0 ? res : res+mod;}
    private static long modpow(long x, long n, long mod) {
        x = mod(x, mod);
        long res = 1;
        while (n > 0) {
            if ((n&1) == 1) res = mod(res*x, mod);
            x = mod(x*x, mod);
            n >>= 1;
        } return res;
    }
    private static long gcd(long a, long b) {return b == 0 ? Math.abs(a) : gcd(b, a % b);}
    private static int gcd(int a, int b) {return b == 0 ? Math.abs(a) : gcd(b, a % b);}
    private static long gcd(long... a) {long gcd=a[0]; for(long x:a) gcd=gcd(gcd, x); return gcd;}
    private static int gcd(int... a) {int gcd=a[0]; for(int x:a) gcd=gcd(gcd, x); return gcd;}
    private static long lcm(long a, long b) {return Math.abs(a / gcd(a, b) * b);}
    private static boolean isEven(int num) {return ((num&1) == 0);}
    private static boolean isOdd(int num) {return !isEven(num);}
    private static boolean isEven(long num) {return ((num&1) == 0);}
    private static boolean isOdd(long num) {return !isEven(num);}
    private static class Pair<T> {
        public T x, y;
        public Pair(T x, T y) {
            this.x = x;
            this.y = y;
        }
        @Override
        public boolean equals(Object obj) {
            if (obj == this) return true;
            if (!(obj instanceof Pair)) return false;
            Pair<T> pair = (Pair<T>)obj;
            return this.x == pair.x && this.y == pair.y;
        }
        @Override
        public String toString() {
            return ("(" + this.x + "," + this.y + ")");
        }
        @Override
        public int hashCode() {
            return (this.x+" "+this.y).hashCode();
        }
    }
    private static class Triplet<T> {
        public T x, y, z;
        public Triplet(T x, T y, T z) {
            this.x = x;
            this.y = y;
            this.z = z;
        }
        @Override
        public boolean equals(Object obj) {
            if (obj == this) return true;
            if (!(obj instanceof Triplet)) return false;
            Triplet<T> triplet = (Triplet<T>)obj;
            return this.x == triplet.x && this.y == triplet.y && this.z == triplet.z;
        }
        @Override
        public String toString() {
            return ("(" + this.x + "," + this.y + "," + this.z + ")");
        }
        @Override
        public int hashCode() {
            return (this.x+" "+this.y+" "+this.z).hashCode();
        }
    }
    ////////////////////////////////////////////////////////////////////////////////////////////////////
    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[8192];
        private int curChar, numChars;
        public InputReader() {
            this.stream = System.in;
        }
        public InputReader(FileInputStream file) {
            this.stream = file;
        }
        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res = (res<<3) + (res<<1) + c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public double nextDouble() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            double res = 0;
            while (!isSpaceChar(c) && c != '.') {
                if (c == 'e' || c == 'E') {
                    return res * Math.pow(10, nextInt());
                }
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            }
            if (c == '.') {
                c = read();
                double m = 1;
                while (!isSpaceChar(c)) {
                    if (c == 'e' || c == 'E') {
                        return res * Math.pow(10, nextInt());
                    }
                    if (c < '0' || c > '9') {
                        throw new InputMismatchException();
                    }
                    m /= 10;
                    res += (c - '0') * m;
                    c = read();
                }
            }
            return res * sgn;
        }

        public long nextLong() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res = (res<<3) + (res<<1) + c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public String next() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }
        public String nextLine() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isEndOfLine(c));
            return res.toString();
        }
        public boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
        private boolean isEndOfLine(int c) {
            return c == '\n' || c == '\r' || c == -1;
        }
    }
    ////////////////////////////////////////////////////////////////////////////////////////////////////
    private static final int mod = 1_000_000_007;
    private static int n, m;
    private static int[] arr;
    static class SegmentTree {
        private long[][] st;
        private SegmentTree() {
            int x = (int)ceil(log(n)/log(2));
            int size = (1<<(x+1))-1;
            st = new long[size][2];
            buildTree(0, 0, n-1);
        }
        private int getMid(int sts, int ste) {
            return (sts+ste)>>1;
        }
        private void buildTree(int sti, int sts, int ste) {
            if (sts == ste) {
                st[sti][0] = st[sti][1] = arr[sts];
                return;
            }
            int mid = getMid(sts, ste);
            buildTree(2*sti+1, sts, mid);
            buildTree(2*sti+2, mid+1, ste);
            st[sti][0] = st[2*sti+1][0] + st[2*sti+2][0];
            st[sti][1] = max(st[2*sti+1][1], st[2*sti+2][1]);
            return;
        }
        private long sumQuery(int sti, int sts, int ste, int qs, int qe) {
            if (qs<=sts && ste<=qe) return st[sti][0];
            if (qs>ste || qe<sts) return 0;
            int mid = getMid(sts, ste);
            return sumQuery(2*sti+1, sts, mid, qs, qe) + sumQuery(2*sti+2, mid+1, ste, qs, qe);
        }
        private void pointUpdate (int sti, int sts, int ste, int ind, int val) {
            if (ind < sts || ind > ste) return;
            if (sts == ste) {
                st[sti][0] = st[sti][1] = val;
                return;
            }
            int mid = getMid(sts, ste);
            pointUpdate(2*sti+1, sts, mid, ind, val);
            pointUpdate(2*sti+2, mid+1, ste, ind, val);
            st[sti][0] = st[2*sti+1][0] + st[2*sti+2][0];
            st[sti][1] = max(st[2*sti+1][1], st[2*sti+2][1]);
            return;
        }
        private void rangeMod(int sti, int sts, int ste, int qs, int qe, int m) {
            if (qs>ste || qe<sts) return;
            if (st[sti][1] < m) return;
            if (sts == ste) {
                st[sti][0] = mod(st[sti][0], m);
                st[sti][1] = mod(st[sti][1], m);
                return;
            }
            int mid = getMid(sts, ste);
            rangeMod(2*sti+1, sts, mid, qs, qe, m);
            rangeMod(2*sti+2, mid+1, ste, qs, qe, m);
            st[sti][0] = st[2*sti+1][0] + st[2*sti+2][0];
            st[sti][1] = max(st[2*sti+1][1], st[2*sti+2][1]);
            return;
        }
    }
    private static void solve() throws Exception {
        n = in.nextInt(); m = in.nextInt();
        arr = new int[n];
        for (int i=0; i<n; i++) arr[i] = in.nextInt();
        SegmentTree segTree = new SegmentTree();
        while (m-->0) {
            int type = in.nextInt();
            if (type == 1) {
                int l = in.nextInt()-1, r = in.nextInt()-1;
                out.printf("%d\n", segTree.sumQuery(0, 0, n-1, l, r));
            } else if (type == 2) {
                int l = in.nextInt()-1, r = in.nextInt()-1, x = in.nextInt();
                segTree.rangeMod(0, 0, n-1, l, r, x);
            } else {
                int k = in.nextInt()-1, x = in.nextInt();
                segTree.pointUpdate(0, 0, n-1, k, x);
            }
        }
    }
    private static void run() throws Exception {
        // in = new InputReader();
        // in = new InputReader(new FileInputStream("input.txt"));
        // out = new PrintWriter(new FileWriter("output.txt"));
        in = oj ? new InputReader() : new InputReader(new FileInputStream("/home/raiden/Desktop/input.txt"));
        out = new PrintWriter(System.out, false);
//        out = new PrintWriter(new FileWriter("/home/raiden/Desktop/output.txt"), false);
        long ti = System.currentTimeMillis();
        solve(); out.flush();
        if (!oj) System.out.println("\n"+(System.currentTimeMillis()-ti)+"ms");
    }
    public static void main(String[] args) throws Exception {run();}
}