最后一个点死活过不去（，想知道是纯粹的常数大还是复杂度问题，常数大的话回去写树状数组了（

#include<bits/stdc++.h>

#define LL long long

#define _ 0

#define R register

// #define AME__DEBUG

using namespace std;

// #define AME__

/*Grievous Lady*/

const int BUF_SIZE = 1 << 12;

char buf[BUF_SIZE] , *buf_s = buf , *buf_t = buf + 1;

#define PTR_NEXT() \
{ \
    buf_s ++; \
    if(buf_s == buf_t) \
    { \
        buf_s = buf; \
        buf_t = buf + fread(buf , 1 , BUF_SIZE , stdin); \
    } \
}

template <typename _m_> inline void mian(_m_ & _n_){
    LL _x_ = 0 , _nega_ = 0;
    while(*buf_s != '-' && !isdigit(*buf_s)) PTR_NEXT(); if(*buf_s == '-'){_nega_ = 1; PTR_NEXT();}
    while(isdigit(*buf_s)){_x_ = _x_ * 10 + *buf_s - '0'; PTR_NEXT();} if(_nega_) _x_ = -_x_; (_n_) = (_x_);
}

inline void put(LL x){
    if (! x) putchar('0');
    if (x < 0) putchar('-'), x = -x;
    int num(0); char c[66];
    while (x) c[++ num] = x % 10 + 48, x /= 10;
    while (num) putchar(c[num --]);
    return (void)(putchar('\n'));
}

// #define int long long

template <typename _n_> bool cmax(_n_ &a , const _n_ &b){ return a < b ? a = b , 1 : 0; }

template <typename _n_> bool cmin(_n_ &a , const _n_ &b){ return a > b ? a = b , 1 : 0; }

const int kato = 2e7 + 10;

const int atri = 2e7;

inline int quick_pow(int a , int b , int mod){
    R int res = 1;
    for(; b ; b >>= 1 , a = 1LL * a * a % mod){
        if(b & 1){
            res = 1LL * res * a % mod;
        }
    }
    return res;
}

LL n , m , cnt , opt , l , r , p , phi[kato] , prime[kato];

bool ispri[kato];

struct tree{
    protected:

        struct node{
            node *ch[2];
            int l , r;
            LL sum , tag;
            node(int l = 0 , int r = 0 , LL sum = 0 , LL tag = 0): l(l) , r(r) , sum(sum) , tag(tag){
                ch[0] = ch[1] = NULL;
            }
            inline int mid(){
                return (l + r) >> 1;
            }
            inline void up(){
                sum = ch[0] -> sum + ch[1] -> sum;
            }
            inline void add_val(LL v){
                tag += v , sum += 1LL * (r - l + 1) * v;
            }
            inline void down(){
                if(tag){
                    ch[0] -> add_val(tag) , ch[1] -> add_val(tag) , tag = 0;
                }
            }
        }*root;

        inline void build(node *&o , int l , int r){
            o = new node(l , r);
            if(l == r){
                mian(o -> sum);
                return;
            }
            build(o -> ch[0] , l , o -> mid()); build(o -> ch[1] , o -> mid() + 1 , r);
            o -> up();
        }

        inline void Modify(node *o , int l , int r , int val){
            if(l <= o -> l && o -> r <= r){
                o -> add_val(val);
                return;
            }
            o -> down();
            if(l <= o -> mid()){
                Modify(o -> ch[0] , l , r , val);
            }
            if(r > o -> mid()){
                Modify(o -> ch[1] , l , r , val);
            }
            o -> up();
        }

        inline LL ask(node *o , int l , int r){
            if(l <= o -> l && o -> r <= r){
                return o -> sum;
            }
            o -> down(); R LL res = 0;
            if(l <= o -> mid()){
                res += ask(o -> ch[0] , l , r);
            }
            if(r > o -> mid()){
                res += ask(o -> ch[1] , l , r);
            }
            return res;
        }

    public:

        inline void build(int n){
            build(root , 1 , n);
        }

        inline void Modify(LL l , LL r , LL val){
            Modify(root , l , r , val);
        }

        inline LL ask(LL x){
            return ask(root , x , x);
        }
}yuni;

inline LL quick_pow_(LL a , LL b , LL mod){
    if(a > INT_MAX) return -1;
    R LL res = 1;
    for(; b ; b >>= 1 , a = a * a){
        if(b & 1){
            if(res * a >= mod) return -1;
            res = res * a;
        }
        if(b > 1 && a * a >= mod) return -1;
    }
    return res;
}

inline bool check(int l , int r , int mod){
    if(r - l + 1 == 5) return 1;
    R LL res = yuni.ask(r);
    if(res >= mod) return 1;
    for(R int i = r - 1 ; i >= l ; i --){
        R int res_ = quick_pow_(yuni.ask(i) , res , mod);
        if(res_ == -1) return 1;
        res = res_;
    }
    return 0;
}

int phi_(int l , int r , int mod){
    if(mod == 1) return 0;
    if(l == r) return yuni.ask(l) % mod;
    R LL tmp = phi_(l + 1 , r , phi[mod]) , pos = l + 1;
    while(pos <= r && yuni.ask(pos) != 1 && pos - l < 6) pos ++;
    if(pos == l + 1 ? phi[mod] <= 1 : check(l + 1 , pos - 1, phi[mod]))
        return quick_pow(yuni.ask(l) % mod , tmp + phi[mod] , mod);
    else return quick_pow(yuni.ask(l) % mod , tmp , mod);
}

inline void pri(){
    for(R int i = 2;i <= atri;i ++){
        if(!ispri[i]){
            prime[++ cnt] = i;
            phi[i] = i - 1;
        }
        for(R int j = 1;j <= cnt && i * prime[j] <= atri;j ++){
            ispri[i * prime[j]] = 1;
            if(i % prime[j] == 0){
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
    }
}

inline int Ame_(){
#ifdef AME__
    freopen("zzq.in" , "r" , stdin); freopen("zzq.out" , "w" , stdout);
#endif
    mian(n) , mian(m);
    pri();
    yuni.build(n);
    for(; m --> 0 ;){
        mian(opt) , mian(l) , mian(r) , mian(p);
        if(opt == 1) yuni.Modify(l , r , p);
        if(opt == 2) put(phi_(l , r , p));
    }
    // fclose(stdin); fclose(stdout);
    return ~~(0^_^0);
}

int Ame__ = Ame_();

signed main(){;}

/*
5 5
2 3 3 3 3
1 1 1 530739835
2 1 1 8356089
2 1 4 5496738
1 1 2 66050181
1 2 4 138625417
*/

/*
6 4
1 2 3 4 5 6
2 1 2 10000007
2 2 3 5
1 1 4 1
2 2 4 10    
*/