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.math.*;


public class D implements Runnable {
	
	void solve() {
		int n = nextInt(), m = nextInt();
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = nextInt();
		FenwickTree ft = new FenwickTree(a);
		SegmentTree st = new SegmentTree(a);
		while (m --> 0) {
			int act = nextInt();
			if (act == 1) {
				int l = nextInt() - 1, r = nextInt() - 1;
				println(ft.sum(l, r));
			} else if (act == 2) {
				int l = nextInt() - 1, r = nextInt() - 1, x = nextInt();
				while (true) {
					int maxInd = st.getMaxInd(l, r), max = st.getValue(maxInd);
					if (max < x)
						break;
					int mod = max % x;
					st.set(maxInd, mod);
					ft.inc(maxInd, mod - max);
				}
			} else {
				int k = nextInt() - 1, x = nextInt(), prev = st.getValue(k);
				st.set(k, x);
				ft.inc(k, x - prev);
			}
		}
	}
	
	class FenwickTree {
		int n;
		long[] t;
		
		FenwickTree(int[] a) {
			this.n = a.length;
			t = new long[n];
			for (int i = 0; i < n; i++)
				inc(i, a[i]);
		}
		
		void inc(int pos, int val) {
			for (int i = pos; i < n; i = (i | (i + 1)))
				t[i] += val;
		}
		
		long sum(int r) {
			long res = 0;
			for (int i = r; i >= 0; i = (i & (i + 1)) - 1)
				res += t[i];
			return res;
		}
		
		long sum(int l, int r) {
			return sum(r) - (l == 0 ? 0 : sum(l - 1));
		}
	}
	
	
	class SegmentTree {
		int n;
		int[] maxInd, data;
		
		SegmentTree(int[] a) {
			this.n = a.length;
			maxInd = new int[n * 4];
			data = new int[n + 1];
			for (int i = 0; i < n; i++)
				data[i] = a[i];
			data[n] = Integer.MIN_VALUE;
			buildTree(1, 0, n - 1, a);
		}
		
		void update(int v) {
			int l = maxInd[v * 2], r = maxInd[v * 2 + 1];
			maxInd[v] = data[l] > data[r] ? l : r;
		}
		
		void buildTree(int v, int tl, int tr, int[] a) {
			if (tl == tr) {
				maxInd[v] = tl;
			} else {
				int tm = (tl + tr) / 2;
				buildTree(v * 2, tl, tm, a);
				buildTree(v * 2 + 1, tm + 1, tr, a);
				update(v);
			}
		}
		
		void set(int pos, int val) {
			set(1, 0, n - 1, pos, val);
		}
		
		void set(int v, int tl, int tr, int pos, int val) {
			if (tl == tr) {
				data[pos] = val;
			} else {
				int tm = (tl + tr) / 2;
				if (pos <= tm)
					set(v * 2, tl, tm, pos, val);
				else
					set(v * 2 + 1, tm + 1, tr, pos, val);
				update(v);
			}
		}
		
		int getValue(int i) {
			return data[i];
		}
		
		int getMaxInd(int l, int r) {
			return getMaxInd(1, 0, n - 1, l, r);
		}
		
		int getMaxInd(int v, int tl, int tr, int l, int r) {
			if (l > r) {
				return n;
			} else if (tl == l && tr == r) {
				return maxInd[v];
			} else {
				int tm = (tl + tr) / 2;
				int f = getMaxInd(v * 2, tl, tm, l, Math.min(tm,  r)), s = getMaxInd(v * 2 + 1, tm + 1, tr, Math.max(tm + 1,  l), r);
				return data[f] > data[s] ? f : s;
			}
		}
	}
	public static void main(String[] args) throws IOException {
		new D().run();
	}
	
	D() {
		this.stream = System.in;
		this.writer = new PrintWriter(System.out);
	}
	
	D(String input, String output) throws IOException {
		File inputFile = new File(input);
		inputFile.createNewFile();
		stream = new FileInputStream(inputFile);
		File outputFile = new File(output);
		outputFile.createNewFile();
		writer = new PrintWriter(outputFile);
	}
	
	public void run() {
		solve();
		writer.close();
	}
	
	void halt() {
		writer.close();
		System.exit(0);
	}
	
	PrintWriter writer;;
	
	void print(Object... objects) {
		for (int i = 0; i < objects.length; i++) {
			if (i != 0)
				writer.print(' ');
			writer.print(objects[i]);
		}
	}
	
	void println(Object... objects) {
		print(objects);
		writer.println();
	}
	
	void printArray(int[] array) {
		for (int i = 0; i < array.length; i++) {
			if (i != 0) writer.print(' ');
			writer.print(array[i]);
		}
		writer.println();
	}
	
	void printArray(long[] array) {
		for (int i = 0; i < array.length; i++) {
			if (i != 0) writer.print(' ');
			writer.print(array[i]);
		}
		writer.println();
	}
	
	void printMatrix(int[][] matrix) {
		for (int i = 0; i < matrix.length; i++)
			printArray(matrix[i]);
	}
	
	void printMatrix(long[][] matrix) {
		for (int i = 0; i < matrix.length; i++)
			printArray(matrix[i]);
	}
	
	/**
	 * Pure Egor's code is straight ahead.
	 */
	
	InputStream stream;
	byte[] buf = new byte[1024];
	int curChar, numChars;
	
	int nextInt() {
		int c = next();
		while (isWhitespace(c))
			c = next();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = next();
		}
		int res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = next();
		} while (!isWhitespace(c));
		return res * sgn;
	}
	
	long nextLong() {
		int c = next();
		while (isWhitespace(c))
			c = next();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = next();
		}
		long res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = next();
		} while (!isWhitespace(c));
		return res * sgn;
	}
	
	double nextDouble() {
		int c = next();
		while (isWhitespace(c))
			c = next();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = next();
		}
		double res = 0;
		while (!isWhitespace(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 = next();
		}
		if (c == '.') {
			c = next();
			double m = 1;
			while (!isWhitespace(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 = next();
			}
		}
		return res * sgn;
	}
	
	BigInteger nextBigInteger() {
		try {
			return new BigInteger(nextString());
		} catch (NumberFormatException e) {
			throw new InputMismatchException();
		}
	}
	
	int next() {
		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++];
	}
	
	String nextString() {
		int c = next();
		while (isWhitespace(c))
			c = next();
		StringBuilder res = new StringBuilder();
		do {
			if (Character.isValidCodePoint(c))
				res.appendCodePoint(c);
			c = next();
		} while (!isWhitespace(c));
		return res.toString();
	}
	
	String nextLine() {
		StringBuilder buf = new StringBuilder();
		int c = next();
		while (c != '\n' && c != -1) {
			if (c != '\r')
				buf.appendCodePoint(c);
			c = next();
		}
		return buf.toString();
	}
	
	boolean EOF() {
		int value;
		while (isWhitespace(value = peek()) && value != -1)
			next();
		return value == -1;
	}
	
	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];
	}
	
	boolean isWhitespace(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}
}