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.*;
import java.util.*;

public class CF438D {
	static int arr[]; 
	public static void main(String [] args) throws Exception{
    	 FastReader in = new FastReader(System.in);
         PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

         int n = in.nextInt() , m = in.nextInt();
         arr = new int[n+1];
         for(int i = 1; i <= n; i++){
        	 arr[i] = in.nextInt();
         }
         
         SegTree segTree = new SegTree(n);
         segTree.build();
         
         for(int i = 1; i <= m; i++){
        	 int type = in.nextInt();
        	 if(type == 1) pw.println(segTree.query(in.nextInt(), in.nextInt()));
        	 else if(type == 2) segTree.update(in.nextInt(), in.nextInt(), in.nextInt());
        	 else segTree.set(in.nextInt(), in.nextInt());
        	 pw.flush();
         }
         
     
         pw.close();
    }
	
	static class SegTree{
		int n;
		long sum[], max[];
		SegTree(int N){
			n = N;
			int maxN = (int)4e5;
			sum = new long[maxN];
			max = new long[maxN];
		}
		
		void build(){
			build(1, 1, n);
		}
		
		void build(int p, int s, int e){
			if(s == e){
				sum[p] = max[p] = arr[s];
				return;
			}
			if(s > e) return;
			int m = (s+e)/2, l = 2*p, r = l+1;
			build(l, s, m);
			build(r, m+1, e);
			sum[p] = sum[l] + sum[r];
			max[p] = Math.max(max[l], max[r]);
		}
		
		void set(int p, int v){
			set(1, 1, n, p, v);
		}
		void set(int p, int s, int e, int pos, int val){
			if(s == pos && e == pos){
				sum[p] = max[p] = arr[s] = val;
				return;
			}
			if(s > e || s > pos || e < pos) return;
			int m = (s+e)/2, l = 2*p, r = l+1;
			set(l, s, m, pos, val);
			set(r, m+1,e, pos, val);
			sum[p] = sum[l] + sum[r];
			max[p] = Math.max(max[l], max[r]);
		}
		
		void update(int a, int b, int m){
			update(1, 1, n, a, b, m);
		}
		void update(int p, int s, int e, int a, int b, int mod){
			if(s == e && s >= a && e <= b && max[p] >= mod){
				max[p] = sum[p] = arr[s] = arr[s] % mod;
				if(max[p] != arr[s]){
					debug("ERROR", a, b, mod);
				}
				return;
			}
			if(s == e) return;
			if(s > e || s > b || e < a) return;
			int m = (s+e)/2, l = 2*p, r = l+1;
			if(max[l] >= mod) update(l, s, m, a, b, mod);
			if(max[r] >= mod) update(r, m+1, e, a, b, mod);
			sum[p] = sum[l] + sum[r];
			max[p] = Math.max(max[l], max[r]);
		}
		
		long query(int a, int b){
			return query(1, 1, n, a, b);
		}
		
		long query(int p, int s, int e, int a, int b){
			if(s >= a && e <= b) return sum[p];
			if(s > e || s > b || e < a) return 0;
			int m = (s+e)/2, l = 2*p, r = l+1;
			return query(l, s, m, a, b) + query(r, m+1, e, a, b);
		}
		
	}
	
    static void debug(Object...obj) {
        System.err.println(Arrays.deepToString(obj));
    }

    static class FastReader {
        InputStream is;
        private byte[] inbuf = new byte[1024];
        private int lenbuf = 0, ptrbuf = 0;
        static final int ints[] = new int[128];

        public FastReader(InputStream is){
            for(int i='0';i<='9';i++) ints[i]=i-'0';
            this.is = is;
        }

        public int readByte(){
            if(lenbuf == -1)throw new InputMismatchException();
            if(ptrbuf >= lenbuf){
                ptrbuf = 0;
                try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
                if(lenbuf <= 0)return -1;
            }
            return inbuf[ptrbuf++];
        }

        public boolean isSpaceChar(int c) {
            return !(c >= 33 && c <= 126);
        }
        public int skip() {
            int b;
            while((b = readByte()) != -1 && isSpaceChar(b));
            return b;
        }

        public String next(){
            int b = skip();
            StringBuilder sb = new StringBuilder();
            while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }
        
        public String nextLine(){
            int b = skip();
            StringBuilder sb = new StringBuilder();
            while(b != '\n'){ 
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }

        public int nextInt(){
            int num = 0, b;
            boolean minus = false;
            while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
            if(b == '-'){
                minus = true;
                b = readByte();
            }

            while(true){
                if(b >= '0' && b <= '9'){
                    num = (num<<3) + (num<<1) + ints[b];
                }else{
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }

        public long nextLong() {
            long num = 0;
            int b;
            boolean minus = false;
            while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
            if(b == '-'){
                minus = true;
                b = readByte();
            }

            while(true){
                if(b >= '0' && b <= '9'){
                    num = (num<<3) + (num<<1) + ints[b];
                }else{
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }
       /* public char nextChar() {
            return (char)skip();
        }*/

        public char[] next(int n){
            char[] buf = new char[n];
            int b = skip(), p = 0;
            while(p < n && !(isSpaceChar(b))){
                buf[p++] = (char)b;
                b = readByte();
            }
            return n == p ? buf : Arrays.copyOf(buf, p);
        }
        
       

        /*private char buff[] = new char[1005];
        public char[] nextCharArray(){
            int b = skip(), p = 0;
            while(!(isSpaceChar(b))){
                buff[p++] = (char)b;
                b = readByte();
            }
            return Arrays.copyOf(buff, p);
        }*/
    }
}