#include using namespace std; #include using namespace atcoder; //高速化 struct ponjuice{ponjuice(){cin.tie(0);ios::sync_with_stdio(0);cout<using vc = vector; templateusing vvc = vc>; templateusing vvvc = vvc>; using vi = vc; using vvi = vvc; using vvvi = vvvc; using vl = vc; using vvl = vvc; using vvvl = vvvc; using pi = pair; using pl = pair; using ull = unsigned ll; templateusing priq = priority_queue; templateusing priqg = priority_queue, greater>; // for文 #define overload4(a, b, c, d, e, ...) e #define rep1(n) for(ll i = 0; i < n; i++) #define rep2(i, n) for(ll i = 0; i < n; i++) #define rep3(i, a, b) for(ll i = a; i < b; i++) #define rep4(i, a, b, step) for(ll i = a; i < b; i+= step) #define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__) #define per1(n) for(ll i = n-1; i >= 0; i--) #define per2(i, n) for(ll i = n-1; i >= 0; i--) #define per3(i, a, b) for(ll i = b-1; i >= a; i--) #define per4(i, a, b, step) for(ll i = b-1; i >= a; i-= step) #define per(...) overload4(__VA_ARGS__, per4, per3, per2, per1)(__VA_ARGS__) #define fore1(a) for(auto&& i : a) #define fore2(i,a) for(auto&& i : a) #define fore3(x,y,a) for(auto&& [x, y] : a) #define fore4(x,y,z,a) for(auto&& [x, y, z] : a) #define fore(...) overload4(__VA_ARGS__, fore4, fore3, fore2, fore1)(__VA_ARGS__) //関数 #define mp make_pair #define mt make_tuple #define pb emplace_back #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define si(x) (ll)(x).size() templateinline bool chmax(S& a, T b){return a < b && ( a = b , true);} templateinline bool chmin(S& a, T b){return a > b && ( a = b , true);} templatevoid uniq(vc&a){sort(all(a));a.erase(unique(all(a)),a.end());} templatevc operator++(vc&v,signed){auto res = v;fore(e,v)e++;return res;} templatevc operator--(vc&v,signed){auto res = v;fore(e,v)e--;return res;} templatevc operator++(vc&v){fore(e,v)e++;return v;} templatevc operator--(vc&v){fore(e,v)e--;return v;} //入出力(operator) templateistream&operator>>(istream&is,static_modint&a){ll v;is>>v;a=v;return is;} istream&operator>>(istream&is,modint&a){ll v;cin>>v;a=v;return is;} templateistream&operator>>(istream&is,pair&a){is>>a.a>>a.b;return is;} templateistream&operator>>(istream&is,vc&a){fore(e,a)is>>e;return is;} templateostream&operator<<(ostream&os,static_modinta){return os<ostream&operator<<(ostream&os,pair&a){return os<ostream&operator<<(ostream&os,set&a){fore(it,a){os<ostream&operator<<(ostream&os,multiset&a){fore(it,a){os<ostream&operator<<(ostream&os,map&a){fore(x,y,a){os<ostream&operator<<(ostream&os,unordered_set&a){fore(it,a){os<ostream&operator<<(ostream&os,unordered_map&a){fore(x,y,a){os<ostream&operator<<(ostream&os,vc&a){fore(e,a)os<ostream&operator<<(ostream&os,vvc&a){fore(e,a)os<>a;return a;} vl readvl(ll n){vl a(n);cin>>a;return a;} vvi readg(ll n,ll m,bool bidirected=true){vvi g(n);rep(i,m){ll a,b;cin>>a>>b;a--;b--;g[a].pb(b);if(bidirected)g[b].pb(a);}return g;} vvcreadgc(ll n,ll m,bool bidirected=true){vvc g(n);rep(i,m){ll a,b,c;cin>>a>>b>>c;a--;b--;g[a].pb(b,c);if(bidirected)g[b].pb(a,c);}return g;} vvi readt(ll n,bool bidirected=true){return readg(n,n-1,bidirected);} vvc readtc(ll n,bool bidirected=true){return readgc(n,n-1,bidirected);} inline void yes(){cout << "Yes\n";} inline void no(){cout << "No\n";} inline void yesno(bool y = true){if(y)yes();else no();} inline void print(){cout<inline void print(T a){cout<inline void print(T a,Ts ...b){cout<>t; while(t--)solve(); } int n,m,k,q; using S = pair>; S op(S l, S r){ #define a first #define b second S res; res.b.b = l.b.b + r.b.b; res.b.a = l.b.a*mint(m).pow(r.b.b) + r.b.a; res.a = (l.b.a * (mint(m).pow(r.b.b+1)-1)/(m-1) - l.b.a) + l.a + r.a; return res; } S e(){ return {mint(0),{mint(0), 0}}; } void solve(){ cin >> n >> m >> k >> q; if(m == 1){ rep(i,q){ cout << 1 << endl; } return; } vi a = readvi(n); segtreetree(n); rep(i,n){ tree.set(i, {mint(a[i] - 1), {mint(a[i]-1),1}}); } rep(i,q){ int c; cin >> c; if(c == 1){ int l,r; cin>> l >> r; l--; auto res = tree.prod(l,r); print((res.second.first * ((mint(m).pow(k-res.second.second + 1) - 1)/(m-1) - 1) + res.first + r - l).val() ); }else{ int x,y; cin >>x >> y; x--; tree.set(x, {mint(y - 1),{mint(y - 1), 1}}); } } }