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.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Scanner;
import java.io.IOException;
import java.io.InputStream;
import java.io.UnsupportedEncodingException;
import java.math.BigInteger;
import java.util.InputMismatchException;

/**
 * Ashesh Vidyut (Drift King) *
 */
public class D {
    public static void main(String[] args) {
        try {
            InputReader in = new InputReader(System.in);
            BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
            int n = in.readInt();
            int m = in.readInt();
            int a[] = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = in.readInt();
            }
            SegmentTree st = new SegmentTree(a);
            for (int i = 0; i < m; i++) {
                int type = in.readInt();
                if(type == 1){
                    int l = in.readInt() - 1;
                    int r = in.readInt() - 1;
                    out.write(Long.toString(st.getAns(l, r)));
                    out.newLine();
                }
                else if(type == 2){
                    int l = in.readInt() - 1;
                    int r = in.readInt() - 1;
                    int x = in.readInt();
                    while(true){
                        int ind = st.maxindexquery(l, r);
                        if(ind == -7)
                            break;
                        if(st.a[ind] >= x){
                            st.a[ind] %= x;
                            st.updateindex(ind, st.a[ind]);
                        }
                        else
                            break;
                    }
                }
                else{
                    int k = in.readInt() - 1;
                    int x = in.readInt();
                    st.a[k] = x;
                    st.updateindex(k, x);
                }
            }
            out.close();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}
class SegmentTree{
    int a[];
    SegmentTreeNode root = null;
    public SegmentTree(int a[]){
        buildTree(a);
        this.a = a;
    }
    public void buildTree(int a[]){
        root = put(root, 0, a.length - 1, a);
    }
    public SegmentTreeNode put(SegmentTreeNode n, int l, int r, int a[]){
        if(n == null){
            n = new SegmentTreeNode(l, r);
        }
        if(l == r){
            n.sumrange = (long)a[l];
            n.right = null;
            n.left = null;
            n.maxind = l;
        }
        else if(l < r){
            int mid = (l + r) / 2;
            n.right = put(n.right, mid + 1, r, a);
            n.left = put(n.left, l, mid, a);
            n.sumrange = (long)n.right.sumrange + (long)n.left.sumrange;
            if(a[n.left.maxind] >= a[n.right.maxind]){
                n.maxind = n.left.maxind;
            }
            else{
                n.maxind = n.right.maxind;
            }
        }
        else{
            return null;
        }
        return n;
    }
    public long getAns(int l, int r){
        return findSum(root, l, r);
    }
    public long findSum(SegmentTreeNode n, int l, int r){
        if(n == null)
            return 0l;
        if(n.l > r || n.r < l){
            return 0l;
        }
        if(n.l >= l && n.r <= r){
            return n.sumrange;
        }
        return findSum(n.left, l, r) + findSum(n.right, l, r);
    }
    public int maxindexquery(int l, int r){
        return findMaxInd(root, l, r);
    }
    public int findMaxInd(SegmentTreeNode n, int l, int r){
        if(n == null){
            return -7;
        }
        if(n.l > r || n.r < l){
            return -7;
        }
        if(n.l >= l && n.r <= r){
            return n.maxind;
        }
        int lmax = findMaxInd(n.left, l, r);
        int rmax = findMaxInd(n.right, l, r);
        if(lmax == -7 && rmax == -7){
            return -7;
        }
        if(lmax == -7)
            return rmax;
        if(rmax == -7)
            return lmax;
        if(a[lmax] >= a[rmax]){
            return lmax;
        }
        return rmax;
    }
    public void updateindex(int k, int x){
        updateTree(root, k, x);
    }
    public void updateTree(SegmentTreeNode n, int k, int x){
        if(n == null)
            return;
        if(n.l > k || n.r < k){
            return;
        }
        if(n.l == n.r && n.l == k){
            n.sumrange = x;
            if(a[n.maxind] < x){
                n.maxind = n.l;
            }
            return ;
        }
        if(n.l <= k && n.r >= k){
            updateTree(n.left, k, x);
            updateTree(n.right, k, x);
            n.sumrange = n.left.sumrange + n.right.sumrange;
            if(a[n.left.maxind] >= a[n.right.maxind]){
                n.maxind = n.left.maxind;
            }
            else
                n.maxind = n.right.maxind;
            return;
        }
        updateTree(n.left, k, x);
        updateTree(n.right, k, x);
        n.sumrange = n.left.sumrange + n.right.sumrange;
        if(a[n.left.maxind] >= a[n.right.maxind]){
            n.maxind = n.left.maxind;
        }
        else
            n.maxind = n.right.maxind;
        return;
    }
}
class SegmentTreeNode{
    public long sumrange;
    public int l, r;
    public int maxind;
    public SegmentTreeNode left, right;
    public SegmentTreeNode(int l, int r){
        this.l = l;
        this.r = r;
        this.left = null;
        this.right = null;
    }
}
class InputReader {
    private boolean finished = false;

    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;

    public InputReader(InputStream stream) {
        this.stream = stream;
    }

    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 peek() {
        if (numChars == -1)
            return -1;
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buf);
            } catch (IOException e) {
                return -1;
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar];
    }

    public int readInt() {
        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 *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public long readLong() {
        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 *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public String readString() {
        int length = readInt();
        if (length < 0)
            return null;
        byte[] bytes = new byte[length];
        for (int i = 0; i < length; i++)
            bytes[i] = (byte) read();
        try {
            return new String(bytes, "UTF-8");
        } catch (UnsupportedEncodingException e) {
            return new String(bytes);
        }
    }

    public static boolean isSpaceChar(int c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    private String readLine0() {
        StringBuffer buf = new StringBuffer();
        int c = read();
        while (c != '\n' && c != -1) {
            if (c != '\r')
                buf.appendCodePoint(c);
            c = read();
        }
        return buf.toString();
    }

    public String readLine() {
        String s = readLine0();
        while (s.trim().length() == 0)
            s = readLine0();
        return s;
    }

    public String readLine(boolean ignoreEmptyLines) {
        if (ignoreEmptyLines)
            return readLine();
        else
            return readLine0();
    }

    public BigInteger readBigInteger() {
        try {
            return new BigInteger(readString());
        } catch (NumberFormatException e) {
            throw new InputMismatchException();
        }
    }

    public char readCharacter() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        return (char) c;
    }

    public double readDouble() {
        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, readInt());
            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, readInt());
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                m /= 10;
                res += (c - '0') * m;
                c = read();
            }
        }
        return res * sgn;
    }

    public boolean isExhausted() {
        int value;
        while (isSpaceChar(value = peek()) && value != -1)
            read();
        return value == -1;
    }

    public String next() {
        return readString();
    }

    public boolean readBoolean() {
        return readInt() == 1;
    }
}