#include 
      
       #include 
       
        #include 
        
         #include 
         
          #define INF 0x3f3f3f3f#define MOD 1000000007#define mem(a,b) memset((a),b,sizeof(a))#define TS printf("!!!\n")#define pb push_back#define pai pair
          
           //using ll = long long;//using ull= unsigned long long;//std::ios::sync_with_stdio(false);using namespace std;//priority_queue
           
            
             ,greater
             
              > que;typedef long long ll;typedef unsigned long long ull;typedef pair
              
                pairint;const double EPS=1e-8;const double PI=acos(-1);const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;const int maxn = 1e5+10;ll a[maxn],mod,ans[maxn];struct node{ int l,r; ll sum,add,mul,lazy; void update(int a,int m,int len){ add = ((ll)(add*m+a))%mod; mul = ((ll)(m*mul))%mod; sum = ((ll)((ll)sum*m+(ll)len*a))%mod; }}tree[maxn<<2];void pushup(int rt){ tree[rt].sum = (tree[rt<<1].sum + tree[rt<<1|1].sum) % mod;}void pushdown(int rt,int len){ if(tree[rt].add!=0 || tree[rt].mul!=1){ tree[rt<<1].update(tree[rt].add,tree[rt].mul,len-(len>>1)); tree[rt<<1|1].update(tree[rt].add,tree[rt].mul,len>>1); tree[rt].add = 0; tree[rt].mul = 1; }}void build(int rt,int l,int r){ tree[rt].l = l, tree[rt].r = r; tree[rt].add = 0, tree[rt].mul = 1; if(l == r) { tree[rt].sum = a[l]; return ; } int mid = (l+r)/2; build(rt<<1,l,mid); build(rt<<1|1,mid+1,r); pushup(rt);}void update(int rt,int l,int r,int add,int mul){ int L = tree[rt].l, R = tree[rt].r; if(l<=L && R<=r){ tree[rt].update(add,mul,R-L+1); return ; } pushdown(rt,R-L+1); int mid = (L+R)/2; if(l<=mid) update(rt<<1,l,r,add,mul); if(r>mid) update(rt<<1|1,l,r,add,mul); pushup(rt);}ll query(int rt,int l,int r){ int L = tree[rt].l, R = tree[rt].r; if(l<=L && R<=r) return tree[rt].sum; else{ ll ans = 0; pushdown(rt,R-L+1); int mid = (L+R)/2; if(l<=mid) ans+=query(rt<<1,l,r)%mod; if(r>mid) ans+=query(rt<<1|1,l,r)%mod; pushup(rt); return ans; }}int main(){ //freopen("input.txt","r",stdin); int n; cin >> n; cin >> mod; for(int i=1; i<=n; i++){ cin >>a[i]; } build(1,1,n); int m; cin >> m; while(m--){ int op; cin >> op; if(op == 1){ //a到b之间乘x int a,b,x; cin >> a >>b >> x; update(1,a,b,0,x); }else if(op == 2){ //a到b之间加x int a,b,add; cin >> a >>b >> add; update(1,a,b,add,1); }else{ int a,b; cin >> a >>b; printf("%lld\n",query(1,a,b)%mod); } } return 0;}