Дерево отрезков (модульная редукция)

n = int(input())
tree = [[0] * 2 for _ in range(n * 4 + 1)]
A = list(map(int, input().split()))

def build(v, l, r):
    if l == r:
        tree[v][0] = A[l]
        tree[v][1] = A[l]
        return
    m = (l + r) // 2
    build(v * 2, l, m)
    build(v * 2 + 1, m + 1, r)
    tree[v][0] = tree[v * 2][0] + tree[v * 2 + 1][0]
    tree[v][1] = max(tree[v * 2][1], tree[v * 2 + 1][1])

def update(v, l, r, z, p):
    if l == r:
        tree[v][0] = z
        tree[v][1] = z
        return
    m = (l + r) // 2
    if p <= m:
        update(v * 2, l, m, z, p)
    else:
        update(v * 2 + 1, m + 1, r, z, p)
    tree[v][0] = tree[v * 2][0] + tree[v * 2 + 1][0]
    tree[v][1] = max(tree[v * 2][1], tree[v * 2 + 1][1])

def get(v, l, r, l0, r0):
    if l == l0 and r == r0:
        return tree[v][0]
    m = (l + r) // 2
    s1 = s2 = 0
    if l0 <= m:
        s1 = get(v * 2, l, m, l0, min(r0, m))
    if r0 >= m + 1:
        s2 = get(v * 2 + 1, m + 1, r, max(l0, m + 1), r0)
    return s1 + s2

def mod(v, l, r, l0, r0, x):
    if tree[v][1] < x:
        return
    if l == r:
        tree[v][0] %= x
        tree[v][1] %= x
        return
    m = (l + r) // 2
    if l0 <= m:
        mod(v * 2, l, m, l0, min(r0, m), x)
    if r0 >= m + 1:
        mod(v * 2 + 1, m + 1, r, max(l0, m + 1), r0, x)
    tree[v][0] = tree[v * 2][0] + tree[v * 2 + 1][0]
    tree[v][1] = max(tree[v * 2][1], tree[v * 2 + 1][1])

build(1, 0, n - 1)
q = int(input())

for i in range(q):
    s = list(map(int, input().split()))
    if s[0] == 1:
        l, r = s[1], s[2]
        update(1, 0, n - 1, r, l - 1)
    elif s[0] == 2:
        l, r, x = s[1], s[2], s[3]
        mod(1, 0, n - 1, l - 1, r - 1, x)
    else:
        l, r = s[1], s[2]
        print(get(1, 0, n - 1, l - 1, r - 1))

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<vector<ll>> tree;
vector<ll> A;

void build(int v, int l, int r) {
    if (l == r) {
        tree[v][0] = A[l];
        tree[v][1] = A[l];
        return;
    }
    int m = (l + r) / 2;
    build(v * 2, l, m);
    build(v * 2 + 1, m + 1, r);
    tree[v][0] = tree[v * 2][0] + tree[v * 2 + 1][0];
    tree[v][1] = max(tree[v * 2][1], tree[v * 2 + 1][1]);
}

void update(int v, int l, int r, ll z, int p) {
    if (l == r) {
        tree[v][0] = z;
        tree[v][1] = z;
        return;
    }
    int m = (l + r) / 2;
    if (p <= m) {
        update(v * 2, l, m, z, p);
    } else {
        update(v * 2 + 1, m + 1, r, z, p);
    }
    tree[v][0] = tree[v * 2][0] + tree[v * 2 + 1][0];
    tree[v][1] = max(tree[v * 2][1], tree[v * 2 + 1][1]);
}

ll get(int v, int l, int r, int l0, int r0) {
    if (l == l0 && r == r0) {
        return tree[v][0];
    }
    int m = (l + r) / 2;
    ll s1 = 0, s2 = 0;
    if (l0 <= m) {
        s1 = get(v * 2, l, m, l0, min(r0, m));
    }
    if (r0 >= m + 1) {
        s2 = get(v * 2 + 1, m + 1, r, max(l0, m + 1), r0);
    }
    return s1 + s2;
}

void mod(int v, int l, int r, int l0, int r0, ll x) {
    if (tree[v][1] < x) return;
    if (l == r) {
        tree[v][0] %= x;
        tree[v][1] %= x;
        return;
    }
    int m = (l + r) / 2;
    if (l0 <= m) {
        mod(v * 2, l, m, l0, min(r0, m), x);
    }
    if (r0 >= m + 1) {
        mod(v * 2 + 1, m + 1, r, max(l0, m + 1), r0, x);
    }
    tree[v][0] = tree[v * 2][0] + tree[v * 2 + 1][0];
    tree[v][1] = max(tree[v * 2][1], tree[v * 2 + 1][1]);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    cin >> n;
    
    A.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> A[i];
    }
    
    tree.assign(4 * n + 1, vector<ll>(2, 0));
    build(1, 0, n - 1);
    
    int q;
    cin >> q;
    
    for (int i = 0; i < q; i++) {
        int type;
        cin >> type;
        
        if (type == 1) {
            int l;
            ll r;
            cin >> l >> r;
            update(1, 0, n - 1, r, l - 1);
        } else if (type == 2) {
            int l, r;
            ll x;
            cin >> l >> r >> x;
            mod(1, 0, n - 1, l - 1, r - 1, x);
        } else {
            int l, r;
            cin >> l >> r;
            cout << get(1, 0, n - 1, l - 1, r - 1) << "\n";
        }
    }
    
    return 0;
}