线段树一开始 $20\tt pts$，后来怎么样也调不好参考了第一篇题解，结果 $30\tt pts$，样例 $1$ 过不了。求大佬指教。

#include <bits/stdc++.h>
#define int long long

using namespace std;

namespace FastIO
{
    struct instream
    {
        int base = 10;

        friend instream &operator>>(instream &in, int &num)
        {
            int flag = 1;
            int ans = 0;
            char ch = getchar();
            while (ch < '0' || ch > '9')
            {
                if (ch == '-')
                {
                    flag = -flag;
                }
                ch = getchar();
            }

            while (ch >= '0' && ch <= '9')
            {
                ans = ans * in.base + (ch - '0');
                ch = getchar();
            }
            num = ans * flag;
            return in;
        }
    };

    struct outstream
    {
        template<typename _CharT, typename _Traits = char_traits<_CharT>>
        struct typ {
            typedef basic_ostream<_CharT, _Traits>& (* end) (basic_ostream<_CharT, _Traits>&);
        };

        int base = 10;

        friend outstream &operator<<(outstream &out, int num)
        {
            if (num < 0)
            {
                putchar('-');
                num = -num;
            }
            if (num >= 10)
            {
                out << num / 10;
            }
            putchar(num % 10 + '0');
            return out;
        }

        friend outstream &operator<<(outstream &out, const char * s) {
            printf("%s", s);
            return out;
        }

        friend outstream &operator<<(outstream &out, string s) {
            cout << s;
            return out;
        }

        friend outstream &operator<<(outstream &out, typ<char>::end e) {
            puts("");
            return out;
        }
    };

    instream fin;
    outstream fout;
}

using namespace FastIO;

const int maxn = 2000001;
const int maxn2 = 20000001;
const int inf = 1e6;
const auto ls = [] (int p) { return p << 1; };
const auto rs = [] (int p) { return p << 1 | 1; };
const auto mid = [] (int l, int r) { return (l + r) >> 1; };

int phi[maxn2], prime[maxn2], cnt;
bool book[maxn2];

void generate() {
    phi[1] = 1;
    for (int i = 2; i <= maxn2; i++) {
        if (!book[i]) {
            prime[++cnt] = i;
            phi[i] = i - 1;
        }
        for (int j = 1; j <= cnt && prime[j] * i <= maxn2; j++) {
            book[prime[j] * i] = true;
            if (i % prime[j] == 0) {
                phi[prime[j] * i] = phi[i] * prime[j];
                break;
            } else {
                phi[prime[j] * i] = phi[i] * (prime[j] - 1);
            }
        }
    } 
}

int power(int base, int freq, int mod) {
    int ans = 1, tmp = base;
    while (freq > 0) {
        if (freq % 2 == 1) ans = ans * tmp % mod;
        freq /= 2;
        tmp = tmp * tmp % mod;
    }
    return ans;
}

struct node {
    int sum;
    int tag;
    int mn;
};

int n, m;
int op, l_, r_, p_;
node tree[maxn << 2];
int arr[maxn];
int last[maxn];

void pushup(int p) {
    tree[p].sum = tree[ls(p)].sum + tree[rs(p)].sum;
    tree[p].mn = min(tree[ls(p)].mn, tree[rs(p)].mn);
}

void pushdown(int p, int l, int r) {
    if (tree[p].tag != 0) {
        tree[ls(p)].tag += tree[p].tag;
        tree[rs(p)].tag += tree[p].tag;
        tree[ls(p)].sum += (tree[p].tag * (mid(l, r) - l + 1));
        tree[rs(p)].sum += (tree[p].tag * (r - mid(l, r)));
        tree[ls(p)].mn = inf;
        tree[rs(p)].mn = inf;
        tree[p].tag = 0;
    }
}

void add(int p, int l, int r, int ql, int qr, int v) {
    if (ql <= l && r <= qr) {
        tree[p].tag += v;
        tree[p].sum += (v * (r - l + 1));
        tree[p].mn = inf;
        return;
    }
    pushdown(p, l, r);
    if (ql <= mid(l, r)) add(ls(p), l, mid(l, r), ql, qr, v);
    if (mid(l, r) < qr) add(rs(p), mid(l, r) + 1, r, ql, qr, v);
    pushup(p);
}

int getsum(int p, int l, int r, int v) {
    if (l == r) {
        return tree[p].sum;
    }
    pushdown(p, l, r);
    int s = 0;
    if (v <= mid(l, r)) s += getsum(ls(p), l, mid(l, r), v);
    else if (mid(l, r) < v) s += getsum(rs(p), mid(l, r) + 1, r, v);
    pushup(p);
    return s;
}

int getp(int p) {
    if (last[p] == m) return arr[p];
    last[p] = m;
    arr[p] = getsum(1, 1, n, p);
    return arr[p];
}  

int getres(int l, int r, int p) {
    if (getp(l) % p == 0) return 0;
    if (p == 1) return 1;
    if (l == r) {
        int s = getp(l);
        if (s >= p) {
            return s % p + p;
        } else {
            return s;
        }
    }
    int f = min(l + 5, r);
    for (int i = l + 1; i <= f; i++) {
        if (getp(i) == 1) {
            f = i;
            break;
        }
    }
    int ls = getp(f);
    int qwq = 0;
    for (int i = f - 1; i > l; i--) {
        qwq = ls;
        ls = 1;
        while (qwq--) {
            ls *= getp(i);
            if (ls >= phi[p]) {
                return power(getp(l) % p, getres(l + 1, r, phi[p]) + phi[p], p); 
            }
        }
    }
    return power(getp(l) % p, ls, p);
}

void build(int p, int l, int r) {
    tree[p].mn = inf;
    if (l == r) {
        if ((tree[p].sum = arr[l]) == 1) {
            tree[p].mn = l;
        }
        return;
    }
    build(ls(p), l, mid(l, r));
    build(rs(p), mid(l, r) + 1, r);
    pushup(p);
}

signed main() {
    memset(last, -1, sizeof(last));
    generate();
    fin >> n >> m;
    for (int i = 1; i <= n; i++) {
        fin >> arr[i];
    }
    build(1, 1, n);
    for (int i = 1; i <= m; i++) {
        fin >> op >> l_ >> r_ >> p_;
        if (op == 1) {
            add(1, 1, n, l_, r_, p_);
        } else {
            fout << getres(l_, r_, p_) % p_ << endl;
        }
    }
    return 0;
}