import java.io.*;
import java.util.*;

public class water_vd_wa2 {

	// val == 0 means getSum query
	class Query {
		int l, r;
		int val;
		int num;

		public Query(int l, int r, int val, int num) {
			super();
			this.l = l;
			this.r = r;
			this.val = val;
			this.num = num;
		}
	}

	public void solve() throws IOException {
		int n = nextInt();
		int max = nextInt();
		int q = nextInt();

		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}

		Query[] queries = new Query[q];
		for (int i = 0; i < q; i++) {
			int type = nextInt();
			if (type == 1) {
				queries[i] = new Query(nextInt() - 1, nextInt() - 1, nextInt(),
						i);
			} else {
				queries[i] = new Query(nextInt() - 1, nextInt() - 1, 0, i);
			}
		}

		ArrayList<Query>[] scanLine = new ArrayList[n + 1];
		for (int i = 0; i <= n; i++) {
			scanLine[i] = new ArrayList<Query>();
		}
		for (int i = 0; i < q; i++) {
			scanLine[queries[i].l].add(queries[i]);
			scanLine[queries[i].r + 1].add(queries[i]);
		}

		ArrayList<Integer>[] fill = new ArrayList[q + 1];
		for (int i = 0; i <= q; i++) {
			fill[i] = new ArrayList<Integer>();
		}
		QueryTree qTree = new QueryTree(q);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < scanLine[i].size(); j++) {
				Query current = scanLine[i].get(j);
				if (current.l == i) {
					qTree.set(current.num, current.val);
				} else {
					qTree.set(current.num, 0);
				}
			}
			fill[qTree.upperBound(max - a[i])].add(i);
//			System.err.println(qTree.upperBound(max - a[i]));
		}

		SumTree sumTree = new SumTree(n, a, max);
		for (int i = 0; i < q; i++) {
			Query cur = queries[i];
			for (int j = 0; j < fill[i].size(); j++) {
				sumTree.fill(fill[i].get(j));
			}
			if (cur.val != 0) {
				sumTree.update(cur.l, cur.r, cur.val);
			} else {
				out.println(sumTree.get(cur.l, cur.r));
			}
		}

	}

	public class SumTree {
		int n;
		final long max;
		int[] cnt;
		long[] update;
		long[] sum;

		public SumTree(int n, int[] a, long max) {
			this.n = n;
			cnt = new int[4 * n + 1];
			update = new long[4 * n + 1];
			sum = new long[4 * n + 1];
			build(0, n - 1, 1, a);
			this.max = max;
		}

		private void build(int l, int r, int pos, int[] a) {
			if (l == r) {
				cnt[pos] = 1;
				sum[pos] = a[l];
				return;
			}
			build(l, (l + r) / 2, pos * 2, a);
			build((l + r) / 2 + 1, r, pos * 2 + 1, a);
			sum[pos] = sum[pos * 2] + sum[pos * 2 + 1];
			cnt[pos] = cnt[pos * 2] + cnt[pos * 2 + 1];
		}

		public void update(int l, int r, int val) {
			update(0, n - 1, l, r, val, 1);
		}

		private void updateNode(int i, int len) {
			cnt[i] = cnt[i * 2] + cnt[i * 2 + 1];
			sum[i] = update[i] * cnt[i] + +sum[i * 2] + sum[i * 2 + 1];
		}

		private void update(int l, int r, int l1, int r1, int val, int i) {
			if (l == l1 && r == r1) {
				update[i] += val;
				sum[i] += val * cnt[i];
				return;
			}
			int mid = (l + r) / 2;
			if (r1 <= mid) {
				update(l, mid, l1, r1, val, i * 2);
			} else if (l1 > mid) {
				update(mid + 1, r, l1, r1, val, i * 2 + 1);
			} else {
				update(l, mid, l1, mid, val, i * 2);
				update(mid + 1, r, mid + 1, r1, val, i * 2 + 1);
			}
			updateNode(i, r - l + 1);
		}

		public void fill(int pos) {
			fill(0, n - 1, pos, 1);
		}

		private void fill(int l, int r, int pos, int i) {
			if (l == r) {
				cnt[i] = 0;
				sum[i] = 0;
				update[i] = 0;
				return;
			}
			int mid = (l + r) / 2;
			if (pos <= mid) {
				fill(l, mid, pos, i * 2);
			} else {
				fill(mid + 1, r, pos, i * 2 + 1);
			}
			updateNode(i, r - l + 1);
		}

		public long get(int l, int r) {
			return getSum(0, n - 1, l, r, 1) + max
					* (r - l + 1 - getCnt(0, n - 1, l, r, 1));
		}

		private long getSum(int l, int r, int l1, int r1, int i) {
			if (l == l1 && r == r1) {
				return sum[i];
			}
			if (update[i] != 0) {
				update[i * 2] += update[i];
				update[i * 2 + 1] += update[i];
				sum[i * 2] = sum[i * 2] + update[i] * cnt[i * 2];
				sum[i * 2 + 1] = sum[i * 2 + 1] + update[i] * cnt[i * 2 + 1];
				update[i] = 0;
			}

			int mid = (l + r) / 2;
			if (r1 <= mid) {
				return getSum(l, mid, l1, r1, i * 2);
			} else if (l1 > mid) {
				return getSum(mid + 1, r, l1, r1, i * 2 + 1);
			} else {
				return getSum(l, mid, l1, mid, i * 2)
						+ getSum(mid + 1, r, mid + 1, r1, i * 2 + 1);
			}
		}

		private long getCnt(int l, int r, int l1, int r1, int i) {
			if (l == l1 && r == r1) {
				return cnt[i];
			}
			int mid = (l + r) / 2;
			if (r1 <= mid) {
				return getCnt(l, mid, l1, r1, i * 2);
			} else if (l1 > mid) {
				return getCnt(mid + 1, r, l1, r1, i * 2 + 1);
			} else {
				return getCnt(l, mid, l1, mid, i * 2)
						+ getCnt(mid + 1, r, mid + 1, r1, i * 2 + 1);
			}
		}

	}

	public class QueryTree {
		int n;
		long[] sum;

		public QueryTree(int n) {
			this.n = n;
			sum = new long[4 * n + 10];
		}

		public void set(int pos, int val) {
			set(0, n, pos, val, 1);
		}

		private void set(int l, int r, int pos, int val, int i) {
			if (l == r) {
				sum[i] = val;
				return;
			}
			if (pos <= (l + r) / 2) {
				set(l, (l + r) / 2, pos, val, i * 2);
			} else {
				set((l + r) / 2 + 1, r, pos, val, i * 2 + 1);
			}
			sum[i] = sum[i * 2] + sum[i * 2 + 1];

		}

		public int upperBound(long sum) {
			return upperBound(0, n, sum, 1);
		}

		private int upperBound(int l, int r, long val, int i) {
			if (l == r) {
				return l;
			}
			int mid = (l + r) / 2;
			if (sum[i * 2] >= val) {
				return upperBound(l, mid, val, i * 2);
			} else {
				return upperBound(mid + 1, r, val - sum[i * 2], i * 2 + 1);
			}

		}

	}

	final String fileName = "water_vd_".split("_")[0];

	public void run() throws IOException {
		br = new BufferedReader(new FileReader(fileName + ".in"));
		out = new PrintWriter(fileName + ".out");
		solve();
		out.close();
		br.close();
	}

	public static void main(String[] args) throws IOException {
		new water_vd_wa2().run();
	}

	BufferedReader br;
	StringTokenizer str;
	PrintWriter out;

	String next() throws IOException {
		while (str == null || !str.hasMoreTokens()) {
			str = new StringTokenizer(br.readLine());
		}
		return str.nextToken();
	}

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

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

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

}
