#緑以下Ex-C

#Segment Tree: O(logN)
class SegmentTree:
    def __init__(self,n,identity_e,combine_f):
        self._n=n;self._size=2  #size=1だとbisectが不便
        while self._size<self._n:self._size<<=1
        self._identity_e=identity_e;self._combine_f=combine_f;self._node=[self._identity_e]*2*self._size
    def build(self,array):
        assert len(array)==self._n,'array too large'
        for i,v in enumerate(array,start=self._size):self._node[i]=v
        for i in range(self._size-1,0,-1):self._node[i]=self._combine_f(self._node[i<<1|0],self._node[i<<1|1])
    def update(self,index,value):  #一点更新
        i=self._size+index;self._node[i]=value
        while i-1:i>>=1;self._node[i]=self._combine_f(self._node[i<<1|0],self._node[i<<1|1])
    def fold(self,L,R):  #区間取得: [L,R)の区間値を得る
        L+=self._size;R+=self._size;vL,vR=[self._identity_e]*2
        while L<R:
            if L&1:vL=self._combine_f(vL,self._node[L]);L+=1
            if R&1:R-=1;vR=self._combine_f(self._node[R],vR)
            L>>=1;R>>=1
        return self._combine_f(vL,vR)
    #down: Falseなら単調増加、Trueなら単調減少を仮定する。
    #[0:Lt]の作用値がX以上/以下 となる、最小のLtを返す。閉区間なので扱い注意。
    def bisect(self,X,down=False):
        now=1; cnt=self._identity_e
        while now<self._size:
            Lt,Rt=self._node[now<<1|0],self._node[now<<1|1]
            if not down and self._combine_f(cnt,Lt)>=X: now=now<<1|0
            elif   down and self._combine_f(cnt,Lt)<=X: now=now<<1|0
            else: cnt=self._combine_f(cnt,Lt); now=now<<1|1
        return now-self._size


#入力受取
N,M,K,Q = map(int,input().split())
A = list(map(lambda x: int(x)-1, input().split()))
MOD = 998244353

#SegTreeに乗せる  TLきついがまずtuple型で乗せてみる
#node = (区間幅, 作用値, 作用値+1)
def node_f(Lt,Rt):
    global M,MOD
    L_dist,L_cnt,L_func = Lt
    R_dist,R_cnt,R_func = Rt
    M_cnt = L_cnt * pow(M,R_dist,MOD) % MOD + R_cnt % MOD
    return (L_dist + R_dist, M_cnt ,(L_func+R_func)%MOD)
ST = SegmentTree(N,(0,0,0),node_f)
ST.build([(1,i,i+1) for i in A])

#クエリを処理
for _ in range(Q):
    t,x,y = map(int,input().split())
    x -= 1
    if t==1:
        _,cnt,func = ST.fold(x,y)
        print((cnt+func+1)%MOD)
    if t==2: ST.update(x, (1,y-1,y))