首先当模数比较小的时候线段树上可以维护 $f(i)$ 表示 $x=i$ 经过该区间内的运算之后得到的值，这样子我们就可以用线段树维护单点修改和查询了。

接着对于前三个点直接暴力，对于后面的点，我们发现模数是合数，分解质因数后发现分解出来都非常的小（$\leq 30$），且数量不超过 $5$。

所以对于每一个分解出来的量用线段树做一遍，用 CRT 合并答案即可。

之的注意的是，分解出来的量是质数的次幂，而不一定是质数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e5;
const int phi[35]={0,1,1,2,2,4,2,6,4,6,4,10,4,12,6,8,8,16,6,18,8,12,10,22,8,20,12,18,12,28};
int test;
int n,m,P;
char s[maxn+5];
char ch[maxn+5];
int a[maxn+5];
inline void Input(int i){
    scanf("%s",s);
    int len=strlen(s);
    ch[i]=s[0];
    a[i]=0;
    for(int j=1;j<len;j++)
        a[i]=10*a[i]+s[j]-'0';
}
inline int Fpow(int x,int y,int mod){
    int res=1;
    if(mod<30) y=y%phi[mod]+phi[mod];
    for(;y;x=x*x%mod,y>>=1)
        if(y&1) res=res*x%mod;
    return res;
}
inline int Calc(int x,int i,int mod){
    if(ch[i]=='+') return (x+a[i])%mod;
    else if(ch[i]=='*') return (x*a[i])%mod;
    else return Fpow(x,a[i],mod);
}
namespace SUB1{
    inline void Solve(){
        int op,x;
        scanf("%lld%lld%lld",&n,&m,&P);
        for(int i=1;i<=n;i++) Input(i);
        while(m--){
            scanf("%lld%lld",&op,&x);
            if(op==1){
                for(int i=1;i<=n;i++) x=Calc(x,i,P);
                printf("%lld\n",x);
            }
            else Input(x);
        }
    }
}
namespace SUB2{
    int p[5],pt;
    int c[5];
    int ans[(maxn<<2)+5][5][30];
    void Modify(int x,int L,int R,int pl){
        if(L==R){
            for(int i=0;i<pt;i++)
                for(int j=0;j<p[i];j++)
                    ans[x][i][j]=Calc(j,pl,p[i]);
        }
        else{
            int mid=((R-L)>>1)+L;
            if(pl<=mid) Modify(x<<1,L,mid,pl);
            else Modify(x<<1|1,mid+1,R,pl);
            for(int i=0;i<pt;i++)
                for(int j=0;j<p[i];j++)
                    ans[x][i][j]=ans[x<<1|1][i][ans[x<<1][i][j]];
        }
    }
    inline void Solve(){
        int op,x;
        scanf("%lld%lld%lld",&n,&m,&P);
        int PP=P;
        for(int i=2;i*i<=P;i++){
            if(PP%i==0){
                int res=1;
                while(PP%i==0) res*=i,PP/=i;
                p[pt++]=res;
            }
        }
        if(PP>1) p[pt++]=PP;
        for(int i=0;i<pt;i++)
            c[i]=1ll*(P/p[i])*Fpow(P/p[i],phi[p[i]]-1,p[i]);
        for(int i=1;i<=n;i++) Input(i),Modify(1,1,n,i);
        while(m--){
            scanf("%lld%lld",&op,&x);
            if(op==1){
                int sum=0;
                for(int i=0;i<pt;i++)
                    sum=(sum+c[i]*ans[1][i][x%p[i]])%P;
                printf("%lld\n",sum);
            }
            else Input(x),Modify(1,1,n,x);
        }
    }
}
signed main(){
    freopen("expr.in","r",stdin);
    freopen("expr.out","w",stdout);
    scanf("%lld",&test);
    if(test<=3) SUB1::Solve();
    else SUB2::Solve();
    return 0;
}