#include <bits/stdc++.h>
#define int long long 
#define M 2001000
using namespace std;
int read() {
	int f(1), x(0);
	char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
	for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
	return f * x;
} 
void write(int x) {
	if (x < 0) putchar('-'), x = -x;
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
struct node {
	int l, r;
	int sum, tag;
} block[M];
int bl[M], a[M], len, t, n, tot, x, y, c, op;
void change(int l, int r, int k) {
	int tl = bl[l], tr = bl[r];
	if (tl == tr) {
		for (int i = l; i <= r; i++)
			a[i] += k;
		block[tl].sum += (r - l + 1) * k;
	} else {
		for (int i = l; i <= block[tl].r; i++)
			a[i] += k;
		block[tl].sum += (block[tl].r - l + 1) * k;
		for (int i = block[tr].l; i <= r; i++)
			a[i] += k;
		block[tr].sum += (r - block[tr].l + 1) * k;
		for (int i = tl + 1; i <= tr - 1; i++) {
			block[i].tag += k;
			block[i].sum += k * len;
		}
	}
}
int query(int l, int r) {
	int ans = 0, tl = bl[l], tr = bl[r];
	if (tl == tr) {
		for (int i = l; i <= r; i++)
			ans += (a[i] + block[i].tag);
		return ans;
	} else {
		for (int i = l; i <= block[tl].r; i++)
			ans += (a[i] + block[i].tag);
		for (int i = block[tr].l; i <= r; i++)
			ans += (a[i] + block[i].tag);
		for (int i = tl + 1; i <= tr - 1; i++)
			ans += block[i].sum;
		return ans;
	}
}
signed main() {
	n = read();
	len = sqrt(n);
	for (int i = 1; i <= n; i++) {
		a[i] = read();
		bl[i] = (i - 1) / len + 1;
		block[bl[i]].sum += a[i];
		if ((i - 1) % len == 0) block[++tot].l = i;
		if (i % len == 0) block[tot].r = i;
	}
	for (int i = 1; i <= n; i++) {
		op = read(), x = read(), y = read(), c = read();
		if (op == 0) change(x, y, c);
		if (op == 1) write(query(x, y) % (c + 1)), putchar('\n');
	}
	return 0;
}