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

public class d438 implements Runnable{
	
    public static void main(String[] args) {
    	try{
            new Thread(null, new d438(), "process", 1<<26).start();
        }
        catch(Exception e){
            System.out.println(e);
        }
    }
	public void run() {
		FastReader scan = new FastReader();
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		//PrintWriter out = new PrintWriter("file.out");
		Task solver = new Task();
		//int t = scan.nextInt();
		int t = 1;
		for(int i = 1; i <= t; i++) solver.solve(i, scan, out);
		out.close();
	}

	static class Task {
		static final int oo = Integer.MAX_VALUE;
		static final long OO = Long.MAX_VALUE;

		public void solve(int testNumber, FastReader sc, PrintWriter out) {
			int N = sc.nextInt();
			int M = sc.nextInt();
			
			long[] arr = readLongArray(N, sc);
			segtMAX max = new segtMAX(N);
			max.build(arr);
			segtSUM sum = new segtSUM(N);
			sum.build(arr);
			//System.out.println(max.queryMax(2, 5));
			while(M --> 0) {
				int type = sc.nextInt();
				if(type == 1) {
					int L = sc.nextInt();
					int R = sc.nextInt();
					out.println(sum.querySum(L-1, R-1));
				} else if(type == 2) {
					int L = sc.nextInt()-1;
					int R = sc.nextInt()-1;
					int X = sc.nextInt();
					tup t = max.queryMax(L, R);
					while(t.max >= X) {
						max.update(t.index, new tup(t.index, t.max % X));
						sum.update(t.index, t.max % X);
						t = max.queryMax(L, R);
					}
				} else {
					int K = sc.nextInt()-1;
					int X = sc.nextInt();
					sum.update(K, X);
					max.update(K, new tup(K, X));
				}
			}
		}
		
		static class segtMAX {
	        tup[] t;
	        int N;
	        public segtMAX(int n) {
	            t = new tup[4*n];
	            N = n;
	        }
	        
	        void build(long a[]) {
	        	build(a, 1, 0, N-1);
	        }
	        
	        void build(long a[], int v, int tl, int tr) {
	            if (tl == tr) {
	                t[v] = new tup(tl, a[tl]);
	            } else {
	                int tm = (tl + tr) / 2;
	                build(a, v*2, tl, tm);
	                build(a, v*2+1, tm+1, tr);
	                if(t[v*2].max > t[v*2+1].max) {
	                	t[v] = t[v*2];
	                } else {
	                	t[v] = t[v*2+1];
	                }
	            }
	        }
	        
	        tup queryMax(int l, int r) {
	        	return queryMax(1, 0, N-1, l, r);
	        }
	 
	        tup queryMax(int v, int tl, int tr, int l, int r) {
	            if (l > r)
	                return new tup(-1, 0);
	            if (l == tl && r == tr)
	                return t[v];
	            int tm = (tl + tr) / 2;
	            tup a = queryMax(v*2, tl, tm, l, Math.min(r, tm));
	            tup b = queryMax(v*2+1, tm+1, tr, Math.max(l, tm+1), r);
	            if(a.max > b.max) {
	            	return a;
	            }
	            return b;
	        }
	        	        
	        void update(int pos, tup new_val) {
	        	update(1, 0, N-1, pos, new_val);
	        }
	 
	        void update(int v, int tl, int tr, int pos, tup new_val) {
	            if (tl == tr) {
	                t[v] = new_val;
	            } else {
	                int tm = (tl + tr) / 2;
	                if (pos <= tm)
	                    update(v*2, tl, tm, pos, new_val);
	                else
	                    update(v*2+1, tm+1, tr, pos, new_val);
	                if(t[v*2].max > t[v*2+1].max) {
	                	t[v] = t[v*2];
	                } else {
	                	t[v] = t[v*2+1];
	                }
	            }
	        }
	    }
		
		static class segtSUM {
	        long[] t;
	        int N;
	        public segtSUM(int n) {
	            t = new long[4*n];
	            N = n;
	        }
	        
	        void build(long a[]) {
	        	build(a, 1, 0, N-1);
	        }
	        
	        void build(long a[], int v, int tl, int tr) {
	            if (tl == tr) {
	                t[v] = a[tl];
	            } else {
	                int tm = (tl + tr) / 2;
	                build(a, v*2, tl, tm);
	                build(a, v*2+1, tm+1, tr);
	                t[v] = (t[v*2] + t[v*2+1]);
	            }
	        }
	        
	        long querySum(int l, int r) {
	        	return querySum(1, 0, N-1, l, r);
	        }
	 
	        long querySum(int v, int tl, int tr, int l, int r) {
	            if (l > r)
	                return 0;
	            if (l == tl && r == tr)
	                return t[v];
	            int tm = (tl + tr) / 2;
	            return querySum(v*2, tl, tm, l, Math.min(r, tm)) + 
	                    querySum(v*2+1, tm+1, tr, Math.max(l, tm+1), r);
	        }
	        
	        void update(int pos, long new_val) {
	        	update(1, 0, N-1, pos, new_val);
	        }
	 
	        void update(int v, int tl, int tr, int pos, long new_val) {
	            if (tl == tr) {
	                t[v] = new_val;
	            } else {
	                int tm = (tl + tr) / 2;
	                if (pos <= tm)
	                    update(v*2, tl, tm, pos, new_val);
	                else
	                    update(v*2+1, tm+1, tr, pos, new_val);
	                t[v] = t[v*2] + t[v*2+1];
	            }
	        }
	    }
	}
	
	static long modDivide(long a, long b, long MOD) {
		a %= MOD;
		return (binpow(b, MOD-2, MOD) * a) % MOD;
	}
	static long binpow(long a, long b, long m) {
		a %= m;
		long res = 1;
		while (b > 0) {
			if ((b & 1) == 1)
				res = res * a % m;
			a = a * a % m;
			b >>= 1;
		}
		return res;
	}
	static int[] reverse(int a[]) 
    { 
        int[] b = new int[a.length]; 
        for (int i = 0, j = a.length; i < a.length; i++, j--) { 
            b[j - 1] = a[i]; 
        } 
        
        return b;
    }
	static long[] reverse(long a[]) 
    { 
        long[] b = new long[a.length]; 
        for (int i = 0, j = a.length; i < a.length; i++, j--) { 
            b[j - 1] = a[i]; 
        } 
        
        return b;
    }
	static void sort(int[] x){
		shuffle(x);
		Arrays.sort(x);
	}
	static void sort(long[] x){
		shuffle(x);
		Arrays.sort(x);
	}
	static class tup {
		int index; long max;
		tup(int a, long b){
			index = a;
			max = b;
		}
		
		public String toString() {
			return "INDEX: " + index + " has max " + max;
		}
	}
	
	static void shuffle(int[] a) {
		Random get = new Random();
		for (int i = 0; i < a.length; i++) {
			int r = get.nextInt(a.length);
			int temp = a[i];
			a[i] = a[r];
			a[r] = temp;
		}
	}

	static void shuffle(long[] a) {
		Random get = new Random();
		for (int i = 0; i < a.length; i++) {
			int r = get.nextInt(a.length);
			long temp = a[i];
			a[i] = a[r];
			a[r] = temp;
		}
	}

	static class FastReader {
		BufferedReader br;
		StringTokenizer st;

		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		public FastReader(String s) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(new File(s)));
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}
	}
	
	static void dbg(int[] arr) {
		System.out.println(Arrays.toString(arr));
	}
	static void dbg(long[] arr) {
		System.out.println(Arrays.toString(arr));
	}
	static void dbg(boolean[] arr) {
		System.out.println(Arrays.toString(arr));
	}

	static void dbg(Object... args) {
        for (Object arg : args)
            System.out.print(arg + " ");
        System.out.println();
    }
	
	static int[] readArray(int size, FastReader in) {
		int[] a = new int[size];
		for(int i = 0; i < size; i++) {
			a[i] = in.nextInt();
		}
		return a;
	}
	
	static long[] readLongArray(int size, FastReader in) {
		long[] a = new long[size];
		for(int i = 0; i < size; i++) {
			a[i] = in.nextLong();
		}
		return a;
	}
}