//UOJ #46
#include<bits/extc++.h>
#include<bits/stdc++.h>
//#pragma GCC optimize(2)
//This code contains niche emotional elements. It is recommended to watch it after the age of 18.
#ifdef __unix__
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#else
#define getchar _getchar_nolock
#define putchar _putchar_nolock
#endif
#define debug(x) fprintf(stderr,"Line %d,%s=%lld\n",__LINE__,#x,(ll)x)
#define debugline fprintf(stderr,"--------------------------\n")
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define Inf (int)INFINITY
#define inf 0x3f3f3f3f
#define pb push_back
#define ll long long
#define endl '\n'
#define y second
#define x first
using namespace std;
const int N=1e5+10;
void read(){};
template<class T1,class...T2>
inline void read(T1&ret,T2&...rest){
ret=0;char c=getchar();bool f=false;
while(c<'0'||c>'9')f=c=='-',c=getchar();
while(c>='0'&&c<='9')ret=ret*10+c-'0',c=getchar();
f&&(ret=-ret),read(rest...);
}
#define cin(...) read(__VA_ARGS__)
template<class T>
inline void print(T x){
static int s[35],t=0;
bool f=x<0;if(f)x=-x;
do s[t++]=x%10,x/=10;while(x);
f&&putchar('-');while(t)putchar(s[--t]+'0');
}
int O,n,q,t,res,a[N];
struct Mod{
using u128=__uint128_t;
using ull=unsigned long long;
void in(){cin(p),*this=p;}Mod(ull mod=998244353){*this=mod;}
explicit operator ull&(){return p;}ull&operator()(){return p;}
Mod&operator=(const ull&mod){return m=((ull)-1)/mod+1,p=mod,*this;}ull m,p;
friend ull operator%(const u128&x,const Mod&self){ull v=x-(((u128)x*(self.m))>>64)*self.p;return min(v,v+self.p);}
}mod;
struct Tag{
int l,r,a,b;
Tag(){};
// Tag(Tag const&)=default;
Tag(int _l,int _r,int _a,int _b):l(_l),r(_r),a(_a),b(_b){}
};
#define vector basic_string
struct Tags:vector<Tag>{
using vector<Tag>::vector;
Tags(){}
Tags(const Tag&t){
if(t.l>1)pb(Tag(1,t.l-1,1,0));
if(pb(t);t.r<n)pb(Tag(t.r+1,n,1,0));
}
};
#undef vector
Tags operator+(const Tags&a,const Tags&b){
Tags res;auto ia=a.begin(),ib=b.begin();
for(int l=1,r;l<=n;l=r+1)
res.pb(Tag(
l,r=min(ia->r,ib->r),
(ia->a*1ll*ib->a)%mod,
(ib->a*1ll*ia->b%mod+ib->b)%mod)),
(r==ia->r?ia:ib)++;
return res;
}
struct SegmentTree{
#define mid ((a[x].l+a[x].r)>>1)
#define rc (x*2+1)
#define lc (x*2)
struct Node{
int l,r;
Tags v;
}a[N*4];
void pushup(int x){a[x].v=a[lc].v+a[rc].v;}
void build(int l,int r,int x=1){
a[x].l=l,a[x].r=r;
if(l^r)
build(l,mid,lc),build(mid+1,r,rc);
}
void insert(int p,Tag v,int x=1){
if(a[x].l==a[x].r)
return a[x].v=Tags(v),void();
insert(p,v,p<=mid?lc:rc);
if(p==a[x].r)pushup(x);
}
void query(int l,int r,int p,int&v,int x=1){
if(l<=a[x].l&&a[x].r<=r){
Tag t=*lower_bound(all(a[x].v),p,
[](const Tag&t,int p)->bool{return t.r<p;});
return v=(v*1ll*t.a%mod+t.b)%mod,void();
}
if(l<=mid)query(l,r,p,v,lc);
if(mid<r)query(l,r,p,v,rc);
}
}tr;
int main(){
// assert(is_trivial<Tag>());
// assert(is_standard_layout<Tag>());
cin(O,n),O&=1,mod.in();
for(int i=1;i<=n;i++)cin(a[i]);
cin(q),tr.build(1,1e5);
for(int op,l,r,x,y;q;q--){
cin(op,l,r),l^=res*O,r^=res*O;
if(op==1)
cin(x,y),tr.insert(++t,Tag(l,r,x,y));
else
cin(x),res=a[x^=res*O],
tr.query(l,r,x,res),print(res),putchar(endl);
}
return 0;
}