Problem: Write a program which manipulates a sequence A = {a1, a2, . . . , an} with the following operations:

* add(s, t, x): add x to as, as+1, ..., at.
* getSum(s, t): report the sum of as, as+1, ..., at.



Note that the initial values of ai (i = 1, 2, . . . , n) are 0.

Constraints

* 1 ≤ n ≤ 100000
* 1 ≤ q ≤ 100000
* 1 ≤ s ≤ t ≤ n
* 0 ≤ x < 1000

Input


n q
query1
query2
:
queryq


In the first line, n (the number of elements in A) and q (the number of queries) are given. Then, ith query queryi is given in the following format:


0 s t x


or


1 s t


The first digit represents the type of the query. '0' denotes add(s, t, x) and '1' denotes getSum(s, t).

Output

For each getSum operation, print the sum;

Examples

Input

3 5
0 1 2 1
0 2 3 2
0 3 3 3
1 1 2
1 2 3


Output

4
8


Input

4 3
1 1 4
0 1 4 1
1 1 4


Output

0
4

Solution (in JAVA):

Solution:
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.NoSuchElementException;

public class Main {

	public static void main(String[] args) {
		new Main();
	}

	public Main() {
		FastScanner sc = new FastScanner();
		int N = sc.nextInt(), Q = sc.nextInt(), q, s, t;
		LazySegmentTree<Long, Long> segment = new LazySegmentTree<Long, Long>(N, 0L, new AdditionLong(), new AdditionLong(), new AdditionLong());
		while(Q-- > 0) {
			q = sc.nextInt();
			s = sc.nextInt() - 1;
			t = sc.nextInt();
			if (q == 0) segment.update(sc.nextLong(), s, t);
			else System.out.println(segment.get(s, t));
		}
	}

	public interface Inverse<T> {
		public T inverse(T element);
	}

	public interface Group<T> extends Monoid<T>, Inverse<T>{

	}

	public interface Abelian<T> extends Group<T>, Commutative<T> {

	}

	public class AdditionLong implements Abelian<Long>, LazySegmentInterface<Long, Long>{

		@Override
		public Long operate(Long left, Long right) {
			return left + right;
		}

		@Override
		public Long unit() {
			return 0L;
		}

		@Override
		public Long inverse(Long element) {
			return -element;
		}

		@Override
		public Long function(Long element, Long reaction, int N) {
			return element + reaction * N;
		}

	}

	public interface Commutative<T> {
	}

	public interface Monoid<T> extends Associative<T>, Unit<T> {
	}

	public interface Unit<T> {
		public T unit();
	}

	public interface Associative<T> {
		public T operate(T left, T right);
	}

	public interface LazySegmentInterface<T, E> {
		public T function(T element, E reaction,  int N);
	}

	public class LazySegmentTree<T, E> {
		private Associative<T> semigroup;
		private Associative<E> lazygroup;
		private LazySegmentInterface<T, E> operate;
		private T dat[];
		private E lazy[];
		private int size;

		public LazySegmentTree(int N, T dat, Associative<T> semigroup, Associative<E> lazygroup, LazySegmentInterface<T, E> operate) {
			this.semigroup = semigroup;
			this.lazygroup = lazygroup;
			this.operate = operate;
			@SuppressWarnings("unchecked")
			T[] data = (T[]) new Object[N];
			Arrays.fill(data, dat);
			build(data);
		}

		public LazySegmentTree(T[] dat, Associative<T> semigroup, Associative<E> lazygroup, LazySegmentInterface<T, E> operate) {
			this.semigroup = semigroup;
			this.lazygroup = lazygroup;
			this.operate = operate;
			build(dat);
		}

		@SuppressWarnings("unchecked")
		private void build(T dat[]) {
			size = dat.length;
			this.dat = (T[]) new Object[Math.max(2, Integer.highestOneBit(dat.length - 1) << 2)]; // 要素数を超える最小の2冪*2
			this.lazy = (E[]) new Object[this.dat.length << 1]; // その遅延評価に使う関数
			System.arraycopy(dat, 0, this.dat, this.dat.length >> 1, dat.length); // 最下段を埋める
			for (int i = this.dat.length / 2 - 1;i > 0; -- i) this.dat[i] = operate(this.dat[i << 1], this.dat[i * 2 + 1]); // 最下段以外すべて、下から埋める
		}

		private void lazy(int index, int length) {
			if (lazy[index] != null) dat[index] = function(index, length);
			lazy[index << 1] = lazyoperate(lazy[index], lazy[index << 1]);
			lazy[index * 2 + 1] = lazyoperate(lazy[index], lazy[index * 2 + 1]);
			lazy[index] = null;
		}

		private void merge(int index, int length) {
			dat[index] = operate(function(index << 1, length >> 1), function(index * 2 + 1, length >> 1));
		}

		private T getLazy(int index, int length) {
			lazy(index, length);
			return dat[index];
		}

		private T operate(T left, T right) {
			if (right == null) return left; // 右がnullの可能性の方がはるかに高いので
			else if (left == null) return right;
			else return semigroup.operate(left, right);
		}

		private void lazyUpdate(E lazy, int index, int length) {
			this.lazy[index] = lazyoperate(this.lazy[index], lazy);
			lazy(index, length);
		}

		private E lazyoperate(E left, E right) {
			if (right == null) return left; // 右がnullの可能性の方がはるかに高いので
			else if (left == null) return right;
			else return lazygroup.operate(left, right);
		}

		private T function(int index, int length) {
			if (lazy[index] != null) return operate.function(dat[index], lazy[index], length);
			return dat[index];
		}

		/**
		 * indexで指定した値に対して更新操作を行います。
		 * @param dat 更新するデータ
		 * @param index 更新する場所
		 */
		public void update(E dat, int index) {
			update(dat, index, index + 1);
		}

		/**
		 * 区間[left, right)に対して更新操作を行います。
		 * @param dat 更新するデータ
		 * @param left 更新する区間の左閉区間
		 * @param right 更新する区間の右開区間
		 */
		public void update(E dat, int left, int right) {
			if (left >= right || right > size) throw new IllegalArgumentException("[" + left + ", " + right + ") is undefined.");
			int mid = left ^ right, m = 1, l, r, length = this.dat.length >> 1;
			while ((mid & length) == 0) { // 共通区間
				if ((left & length) != 0) { // 右側だったので1個移動
					left &= ~length;
					right &= ~length;
					++ m;
				}
				lazy(m, length); // 境界を見つけるまで遅延評価
				m <<= 1;
				length >>= 1;
			} // この時点で左と右は違う区間を指す
			l = m;
			int lengthL = length;
			while(left != 0) { // 左側評価開始
				lazy(l, lengthL);
				l <<= 1;
				lengthL >>= 1;
				if ((left & lengthL) == 0) { // 1個右は含まれる区間なので
					lazyUpdate(dat, l + 1, lengthL);
				} else {
					left &= ~lengthL;
					++ l;
				}
			}
			lazyUpdate(dat, l, lengthL);
			r = m + 1;
			int lengthR = length;
			right &= ~lengthR;
			while(right != 0) { // 右側評価開始
				lazy(r, lengthR);
				r <<= 1;
				lengthR >>= 1;
				if ((right & lengthR) != 0) { // 1個左は含まれる区間なので
					right &= ~lengthR;
					lazyUpdate(dat, r, lengthR);
					++ r;
				}
			}
			// これで全ての遅延評価が終わったので、次は戻していく操作
			while(l > m) {
				l >>= 1;
				lengthL <<= 1;
				merge(l, lengthL);
			}
			++ m;
			while(r > m) {
				r >>= 1;
				lengthR <<= 1;
				merge(r, lengthR);
			}
			-- m;
			while(m > 1) {
				m >>= 1;
				length <<= 1;
				merge(m, length);
			}
		}

		public T get(int index) {
			return get(index, index + 1);
		}

		public T get(int left, int right) {
			if (left >= right || right > size) throw new IllegalArgumentException("[" + left + ", " + right + ") is undefined.");
			int mid = left ^ right, m = 1, l, r, length = this.dat.length >> 1;
			T ret = null;
			while ((mid & length) == 0) { // 共通区間
				if ((left & length) != 0) { // 右側だったので1個移動
					left &= ~length;
					right &= ~length;
					++ m;
				}
				lazy(m, length); // 境界を見つけるまで遅延評価
				m <<= 1;
				length >>= 1;
			} // この時点で左と右は違う区間を指す
			l = m;
			int lengthL = length;
			while(left != 0) { // 左側評価開始
				lazy(l, lengthL);
				l <<= 1;
				lengthL >>= 1;
				if ((left & lengthL) == 0) { // 1個右は含まれる区間なので
					ret = operate(getLazy(l + 1, lengthL), ret);
				} else {
					left &= ~lengthL;
					++ l;
				}
			}
			ret = operate(getLazy(l, lengthL), ret);
			r = m + 1;
			int lengthR = length;
			right &= ~lengthR;
			while(right != 0) { // 右側評価開始
				lazy(r, lengthR);
				r <<= 1;
				lengthR >>= 1;
				if ((right & lengthR) != 0) { // 1個左は含まれる区間なので
					right &= ~lengthR;
					ret = operate(ret, getLazy(r++, lengthR));
				}
			}
			// これで全ての遅延評価が終わったので、次は戻していく操作
			while(l > m) {
				l >>= 1;
				lengthL <<= 1;
				merge(l, lengthL);
			}
			++ m;
			while(r > m) {
				r >>= 1;
				lengthR <<= 1;
				merge(r, lengthR);
			}
			-- m;
			while(m > 1) {
				m >>= 1;
				length <<= 1;
				merge(m, length);
			}
			return ret;
		}
	}



	public class FastScanner {
		private final InputStream in = System.in;
		private final byte[] buffer = new byte[1024];
		private int ptr = 0;
		private int buflen = 0;

		private boolean hasNextByte() {
			if (ptr < buflen) {
				return true;
			} else {
				ptr = 0;
				try {
					buflen = in.read(buffer);
				} catch (IOException e) {
					e.printStackTrace();
				}
				if (buflen <= 0) {
					return false;
				}
			}
			return true;
		}

		private int readByte() {
			if (hasNextByte()) return buffer[ptr++];
			else return -1;
		}

		private boolean isPrintableChar(int c) {
			return 33 <= c && c <= 126;
		}

		public boolean hasNext() {
			while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;
			return hasNextByte();
		}

		public String next() {
			if (!hasNext()) throw new NoSuchElementException();
			StringBuilder sb = new StringBuilder();
			int b = readByte();
			while (isPrintableChar(b)) {
				sb.appendCodePoint(b);
				b = readByte();
			}
			return sb.toString();
		}

		public long nextLong() {
			if (!hasNext()) throw new NoSuchElementException();
			long n = 0;
			boolean minus = false;
			int b = readByte();
			if (b == '-') {
				minus = true;
				b = readByte();
			}
			if (b < '0' || '9' < b) throw new NumberFormatException();
			while (true) {
				if ('0' <= b && b <= '9') {
					n *= 10;
					n += b - '0';
				} else if (b == -1 || !isPrintableChar(b)) return minus ? -n : n;
				else throw new NumberFormatException();
				b = readByte();
			}
		}

		public int nextInt() {
			long nl = nextLong();
			if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
			return (int) nl;
		}

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

		public int[] nextInt(int width) {
			int[] ret = new int[width];
			for (int i = 0;i < width;++ i) ret[i] = nextInt();
			return ret;
		}

		public long[] nextLong(int width) {
			long[] ret = new long[width];
			for (int i = 0;i < width;++ i) ret[i] = nextLong();
			return ret;
		}

		public int[][] nextInt(int width, int height) {
			int[][] ret = new int[height][width];
			for (int i = 0, j;i < height;++ i) for (j = 0;j < width;++ j) ret[j][i] = nextInt();
			return ret;
		}

		public long[][] nextLong(int width, int height) {
			long[][] ret = new long[height][width];
			for (int i = 0, j;i < height;++ i) for (j = 0;j < width;++ j) ret[j][i] = nextLong();
			return ret;
		}
	}

}