Untitled

#include "bits/stdc++.h"
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x...)
#endif

using ll = long long;
using db = long double;

#define int long long

struct segtree {

    struct node {
        ll v, h;
    };

    int size;
    vector<node> tree;

    segtree(int n) {
        size = 1;
        while (size < n) size *= 2;
        tree.assign(2 * size - 1, {0, 0});
    }

    void modify(int l, int r, ll v, int x, int lx, int rx) {
        if (lx >= r || rx <= l) {
            return;
        } else if (lx >= l && rx <= r) {
            tree[x] = {tree[x].v + v * (rx - lx), tree[x].h + v};
        } else {
            int m = (lx + rx) / 2;
            modify(l, r, v, x * 2 + 1, lx, m);
            modify(l, r, v, x * 2 + 2, m, rx);
            tree[x] = {(tree[x * 2 + 1].v + tree[x * 2 + 2].v) + tree[x].h * (rx - lx), tree[x].h};
        }
    }

    void modify(int l, int r, ll v) {
        modify(l, r, v, 0, 0, size);
    }

    ll calc(int l, int r, int x, int lx, int rx) {
        if (lx >= r || rx <= l) {
            return 0;
        } else if (lx >= l && rx <= r) {
            return tree[x].v;
        } else {
            int m = (lx + rx) / 2;
            return (calc(l, r, x * 2 + 1, lx, m) + calc(l, r, x * 2 + 2, m, rx)) + tree[x].h * (min(rx, r) - max(lx, l));
        }
    }

    ll calc(int l, int r) {
        return calc(l, r, 0, 0, size);
    }

};

constexpr int S = 2000;

void test_case() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<ll> pa(n + 1);
    for (int i = 1; i <= n; i++) {
        pa[i] = pa[i - 1] + a[i - 1];
    }
    segtree tree1(n);
    map<int, ll> mp;
    int m;
    cin >> m;
    for (int i = 0; i < m; i++) {
        int t;
        cin >> t;
        if (t == 1) {
            int l, r, c;
            cin >> l >> r >> c;
            l--; r--;
            tree1.modify(l, r + 1, c);
        } else if (t == 2) {
            int d, c;
            cin >> d >> c;
            if (d > S) {
                for (int i = d - 1; i < n; i += d) {
                    tree1.modify(i, i + 1, c);
                }
            } else {
                mp[d] += c;
            }
        } else {
            int l, r;
            cin >> l >> r;
            l--; r--;
            ll pl = 0;
            for (auto &[v, c] : mp) {
                pl += ((r + 1) / v - l / v) * c;
            }
            cout << pa[r + 1] - pa[l] + tree1.calc(l, r + 1) + pl << endl;
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tests = 1;
    // cin >> tests;
    while (tests--) {
        test_case();
    }
    return 0;
}