所以平衡树真的卡过不去吗。。。

#include <random>
#include <cstdio>
#include <vector>
using std :: vector;
using std :: mt19937;

template <typename T>
inline void read(T &x){
    x = 0;int fu = 1;
    char c = getchar();
    while(c > 57 || c < 48){
        if(c == 45) fu = -1;
        c = getchar();
    }
    while(c <= 57 && c >= 48){
        x = (x << 3) + (x << 1) + c - 48;
        c = getchar();
    }
    x *= fu;
}
template <typename T>
inline void fprint(T x){
    if(x < 0) putchar(45), x = -x;
    if(x > 9) fprint(x / 10);
    putchar(x % 10 + 48);
}
template <typename T>
inline void fprint(T x, char ch){
    fprint(x);putchar(ch);
}

#define MAXN 100005
#define MEMORY 23000005
typedef long long LL;
int a[MAXN], n, m;
mt19937 rnd(19260817);
vector <int> v[MAXN * 5];
int b[MAXN], cnt;
int prime[MAXN], p;
int vis[MAXN * 5];
inline void sieve(){
    for (register int i = 2;i <= 500000;i ++){
        if(!vis[i]) prime[++ p] = i, vis[i] = i;
        for (register int j = 1;j <= p && prime[j] * i <= 500000;j ++){
            vis[i * prime[j]] = prime[j];
            if(i % prime[j] == 0) break;
        }
    }
}
int tot, root[MAXN * 5], lc[MEMORY], rc[MEMORY], val[MEMORY], rd[MEMORY];
LL c[MAXN];
inline int lowbit(int x){return x & -x;}
inline void modify(int x, int y){for (;x <= n;x += lowbit(x)) c[x] += y;}
inline LL query(int x){LL ret = 0;for (;x;x -= lowbit(x)) ret += c[x];return ret;}
int build(int l, int r){
    int mid = (l + r) >> 1;
    val[++ tot] = b[mid];
    rd[tot] = rnd();
    int rt = tot;
    if(l < mid) lc[rt] = build(l, mid - 1); 
    if(r > mid) rc[rt] = build(mid + 1, r);
    return rt;
}
void split(int rt, int k, int &x, int &y){
    if(!rt) x = y = 0;
    else if(val[rt] <= k) {x = rt;split(rc[rt], k, rc[rt], y);}
    else {y = rt;split(lc[rt], k, x, lc[rt]);}
}
int merge(int x, int y){
    if(!x || !y) return x | y;
    if(rd[x] <= rd[y]){
        rc[x] = merge(rc[x], y);
        return x;
    }
    else{
        lc[y] = merge(x, lc[y]);
        return y;
    }
}
void dfs(int x, int e){
    if(lc[x]) dfs(lc[x], e);
    int k = val[x];
    if(a[k] % e == 0){
        modify(k, (a[k] / e) - a[k]);
        a[k] /= e;
        if(a[k] % e == 0) b[++ cnt] = k;
    }
    if(rc[x]) dfs(rc[x], e);
}
void work(int l, int r, int x){
    int rt1, rt2, rt3;
    split(root[x], l - 1, rt1, rt2);
    split(rt2, r, rt2, rt3);
    cnt = 0;
    if(rt2) {
        dfs(rt2, x);
        if(cnt) rt2 = build(1, cnt);
        else rt2 = 0;
    }
    root[x] = merge(rt1, merge(rt2, rt3));
}
int d[MAXN * 5], cur;
int main(){
    read(n);read(m);sieve();
    for (register int i = 1;i <= n;i ++) {
        read(a[i]);modify(i, a[i]);
        cur = 1;d[cur] = 1;
        int x = a[i];
        for (register int j = 1;j <= p && prime[j] * prime[j] <= x;j ++){
            int cc = 0;
            while(x % prime[j] == 0){
                cc ++;
                x /= prime[j];
            }
            int tmp = cur, var = 1;
            while(cc --){
                var *= prime[j];
                for (register int k = 1;k <= cur;k ++){
                    d[++ tmp] = d[k] * var;
                }
            }
            cur = tmp;
        }
        if(x > 1){
            int tmp = cur;
            for (register int k = 1;k <= cur;k ++){
                d[++ tmp] = d[k] * x;
            }
            cur = tmp;
        }
        for (register int k = 2;k <= cur;k ++){
            v[d[k]].push_back(i);
        }
    }
    for (register int i = 2;i <= 500000;i ++) {
        cnt = 0;
        for (auto it : v[i]){
            b[++ cnt] = it;
        }
        if(cnt) root[i] = build(1, cnt);
    }
    LL ans = 0;
    while(m --){
        int opt;
        LL l, r, x;
        read(opt);read(l);read(r);
        l ^= ans;r ^= ans;
        if(opt == 1){
            read(x);x ^= ans;
            if(x == 1) continue;
            work(l, r, x);
        }
        else{
            fprint(ans = query(r) - query(l - 1), 10);
        }
    }
}