class Modulo_Polynomial:
    __slots__= ("poly", "max_degree")

    def __init__(self, poly: list[int] = None, max_degree: int = 2 * 10 ** 5):
        """ 多項式を定義する (各係数の法 Mod はグローバル変数から指定する).

        Args:
            poly (list[int], optional): 係数のリスト. 第 d 要素は d 次の係数を表す. None のときは [0] と同義. Defaults to None.
            max_degree (int, optional): (mod X^n) を考えるときの n. Defaults to 2*10**5.
        """

        if poly is None:
            poly = [0]

        self.poly: list[int] = [a % Mod for a in poly[:max_degree]]
        self.max_degree = max_degree

    def __str__(self) -> str:
        return str(self.poly)

    def __repr__(self) -> str:
        return f"{self.__class__.__name__}({self.poly})"

    def __iter__(self):
        yield from self.poly

    def __eq__(self, other: "Modulo_Polynomial") -> bool:
        from itertools import zip_longest
        return all([a == b for a, b in zip_longest(self.poly, other.poly, fillvalue = 0)])

    #+,-
    def __pos__(self) -> "Modulo_Polynomial":
        return self

    def __neg__(self) -> "Modulo_Polynomial":
        return self.scale(-1)

    #items
    def __getitem__(self, index):
        if isinstance(index, slice):
            return Modulo_Polynomial(self.poly[index], self.max_degree)
        else:
            if index<0:
                raise IndexError(f"index is negative (index: {index})")
            elif index>=len(self.poly):
                return 0
            else:
                return self.poly[index]

    def __setitem__(self, index, value):
        if index<0:
            raise IndexError(f"index is negative (index: {index})")
        elif index>=self.max_degree:
            return

        if index>=len(self.poly):
            self.poly+=[0]*(index-len(self.poly)+1)
        self.poly[index]=value%Mod

    #Boole
    def __bool__(self) -> bool:
        return any(self.poly)

    #簡略化
    def reduce(self):
        """ 先頭の 0 を削除する.
        """

        poly = self.poly
        while poly and (poly[-1] == 0):
            poly.pop()


    #シフト
    def __lshift__(self, depth: int) -> "Modulo_Polynomial":
        if depth < 0:
            return self >> (-depth)

        if depth > self.max_degree:
            return Modulo_Polynomial([0], self.max_degree)

        return Modulo_Polynomial([0] * depth + self.poly, self.max_degree)

    def __rshift__(self, depth: int) -> "Modulo_Polynomial":
        if depth < 0:
            return  self << (-depth)

        return Modulo_Polynomial(self.poly[depth:], self.max_degree)

    #次数
    def degree(self) -> int:
        """ この多項式の次数を求める.

        Returns:
            int: 次数 (係数が 0 ではない最大次数)
        """

        for d in range(len(self.poly) - 1, -1, -1):
            if self.poly[d]:
                return d
        else:
            return -float("inf")

    #加法
    def __add__(self, other) -> "Modulo_Polynomial":
        P=self; Q=other

        if Q.__class__==Modulo_Polynomial:
            N=min(P.max_degree,Q.max_degree)
            A=P.poly; B=Q.poly
        else:
            N=P.max_degree
            A=P.poly; B=Q
        return Modulo_Polynomial(Calc.add(A, B), N)

    def __radd__(self, other) -> "Modulo_Polynomial":
        return self+other

    #減法
    def __sub__(self, other) -> "Modulo_Polynomial":
        P=self; Q=other
        if Q.__class__==Modulo_Polynomial:
            N=min(P.max_degree,Q.max_degree)
            A=P.poly; B=Q.poly
        else:
            N=P.max_degree
            A=P.poly; B=Q
        return Modulo_Polynomial(Calc.sub(A, B), N)

    def __rsub__(self, other) -> "Modulo_Polynomial":
        return (-self) + other

    #乗法
    def __mul__(self, other) -> "Modulo_Polynomial":
        P=self
        Q=other
        if Q.__class__==Modulo_Polynomial:
            a=b=0
            for x in P.poly:
                if x:
                    a+=1
            for y in Q.poly:
                if y:
                    b+=1

            if a>b:
                P,Q=Q,P

            P.reduce();Q.reduce()
            U,V=P.poly,Q.poly
            M=min(P.max_degree,Q.max_degree)
            if a<2*P.max_degree.bit_length():
                B=[0]*(len(U)+len(V)-1)
                for i in range(len(U)):
                    if U[i]:
                        for j in range(len(V)):
                            B[i+j]+=U[i]*V[j]
                            if B[i+j]>Mod:
                                B[i+j]-=Mod
            else:
                B=Calc.convolution(U,V)[:M]
            B=Modulo_Polynomial(B,M)
            B.reduce()
            return B
        else:
            return self.scale(other)

    def __rmul__(self, other) -> "Modulo_Polynomial":
        return self.scale(other)

    #除法
    def __floordiv__(self, other) -> "Modulo_Polynomial":
        if not other:
            raise ZeroDivisionError
        if isinstance(other,int):
            return self/other

        self.reduce()
        other.reduce()

        return Modulo_Polynomial(Calc.flood_div(self.poly, other.poly), max(self.max_degree, other.max_degree))

    def __rfloordiv__(self, other) -> "Modulo_Polynomial":
        if not self:
            raise ZeroDivisionError

        if isinstance(other,int):
            return Modulo_Polynomial([],self.max_degree)

    #剰余
    def __mod__(self, other) -> "Modulo_Polynomial":
        if not other:
            return ZeroDivisionError
        self.reduce(); other.reduce()
        r = Modulo_Polynomial(Calc.mod(self.poly, other.poly), min(self.max_degree, other.max_degree))
        r.reduce()
        return r

    def __rmod__(self, other) -> "Modulo_Polynomial":
        if not self:
            raise ZeroDivisionError
        r=other-(other//self)*self
        r.reduce()
        return r

    def __divmod__(self, other) -> tuple["Modulo_Polynomial", "Modulo_Polynomial"]:
        q=self//other
        r=self-q*other; r.reduce()
        return (q,r)

    #累乗
    def __pow__(self, other) -> "Modulo_Polynomial":
        if other.__class__==int:
            n=other
            m=abs(n)

            Q=self
            A=Modulo_Polynomial([1],self.max_degree)
            while m>0:
                if m&1:
                    A*=Q
                m>>=1
                Q*=Q

            if n>=0:
                return A
            else:
                return A.inverse()
        else:
            P=Log(self)
            return Exp(P*other)

    def inverse(self, deg: int = None) -> "Modulo_Polynomial":
        """ この多項式の (mod X^d) での逆元を求める.

        Args:
            deg (int, optional): 逆元の精度 ((mod X^d) の逆元を求める際の d) を指定する. None のときは元の多項式の精度をそのまま採用. Defaults to None.

        Returns:
            Modulo_Polynomial: _description_
        """
        assert self.poly[0], "定数項が0"

        if deg is None:
            deg = self.max_degree

        return Modulo_Polynomial(Calc.inverse(self.poly, deg), self.max_degree)

    #除法
    def __truediv__(self, other) -> "Modulo_Polynomial":
        if isinstance(other, Modulo_Polynomial):
            if Calc.is_sparse(other.poly):
                d,f=Calc.coefficients_list(other.poly)
                K=len(d)
                H=[0]*self.max_degree

                alpha=pow(other[0], -1, Mod)
                H[0]=alpha*self[0]%Mod

                for i in range(1, self.max_degree):
                    c=0
                    for j in range(1, K):
                        if d[j]<=i:
                            c+=f[j]*H[i-d[j]]%Mod
                        else:
                            break
                    c%=Mod
                    H[i]=alpha*(self[i]-c)%Mod
                H=Modulo_Polynomial(H, min(self.max_degree, other.max_degree))
                return H
            else:
                return self*other.inverse()
        else:
            return pow(other, -1, Mod)*self

    def __rtruediv__(self, other: "Modulo_Polynomial") -> "Modulo_Polynomial":
        return other*self.inverse()

    #スカラー倍
    def scale(self, s: int) -> "Modulo_Polynomial":
        """ 多項式に s 倍を掛けた多項式を求める.

        Args:
            s (int): スカラー倍の係数

        Returns:
            Modulo_Polynomial: s 倍した多項式
        """

        return Modulo_Polynomial(Calc.times(self.poly,s), self.max_degree)

    #最高次の係数
    def leading_coefficient(self) -> int:
        """ 最高次の係数を求める

        Returns:
            int: 最高次の係数 (0 多項式の返り値は 0 とする)
        """

        for a in self.poly[::-1]:
            if a:
                return a
        else:
            return 0

    def censor(self, m: int = None):
        """ m 次以降の係数を切り捨てる.

        Args:
            m (int, optional): 切り捨てる精度. Defaults to None.
        """

        if m is None:
            m = self.max_degree

        m = min(m, self.max_degree)
        del self.poly[m:]

    def resize(self, m: int):
        """ この多項式の情報を持っている配列の長さを m にする (短い場合は末尾に 0 を追加し, 長い場合は m 次以上を切り捨てる).

        Args:
            m (int): 次数
        """
        m = min(m, self.max_degree)
        if len(self.poly) > m:
            del self.poly[:m]
        elif len(self.poly) < m:
            self.poly.extend([0] * (m - len(self.poly)))

    #代入
    def substitution(self, a: int) -> int:
        """ 多項式の変数に a を形式的に代入した式の値を求める.

        Args:
            a (int): 代入する値

        Returns:
            int: 式の値
        """

        y = 0
        a_pow = 1
        for p in self.poly:
            y += p * a_pow % Mod
            a_pow = (a_pow * a) % Mod
        return y % Mod

    def order(self, default: int = None) -> int:
        """ この形式的ベキ級数の位数 (係数が 0 でない次数のうちの最低次数) を求める.

        Args:
            default (int, optional): ゼロ多項式の返り値. Defaults to None.

        Returns:
            int: 位数
        """

        for d in range(len(self.poly)):
            if self.poly[d]:
                return d
        else:
            return default

#=================================================
class Calculator:
    def __init__(self):
        self.primitive = self.__primitive_root()
        self.__build_up()

    def __primitive_root(self) -> int:
        """ Mod の原始根を求める.

        Returns:
            int: Mod の原始根
        """

        p = Mod
        if p == 2:
            return 1
        if p == 998244353:
            return 3
        if p == 10**9 + 7:
            return 5
        if p == 163577857:
            return 23
        if p == 167772161:
            return 3
        if p == 469762049:
            return 3

        fac=[]
        q=2
        v=p-1

        while v>=q*q:
            e=0
            while v%q==0:
                e+=1
                v//=q

            if e>0:
                fac.append(q)
            q+=1

        if v>1:
            fac.append(v)

        for g in range(2, p):
            if pow(g, p-1, p) != 1:
                return None

            flag=True
            for q in fac:
                if pow(g, (p-1) // q, p) == 1:
                    flag = False
                    break

            if flag:
                return g

    #参考元: https://judge.yosupo.jp/submission/72676
    def __build_up(self):
        rank2=(~(Mod-1) & ((Mod-1)-1)).bit_length()
        root=[0]*(rank2+1); iroot=[0]*(rank2+1)
        rate2=[0]*max(0, rank2-1); irate2=[0]*max(0, rank2-1)
        rate3=[0]*max(0, rank2-2); irate3=[0]*max(0, rank2-2)

        root[-1]=pow(self.primitive, (Mod-1)>>rank2, Mod)
        iroot[-1]=pow(root[-1], -1, Mod)

        for i in range(rank2)[::-1]:
            root[i]=root[i+1]*root[i+1]%Mod
            iroot[i]=iroot[i+1]*iroot[i+1]%Mod

        prod=iprod=1
        for i in range(rank2-1):
            rate2[i]=root[i+2]*prod%Mod
            irate2[i]=iroot[i+2]*prod%Mod
            prod*=iroot[i+2]; prod%=Mod
            iprod*=root[i+2]; iprod%=Mod

        prod=iprod = 1
        for i in range(rank2-2):
            rate3[i]=root[i + 3]*prod%Mod
            irate3[i]=iroot[i + 3]*iprod%Mod
            prod*=iroot[i + 3]; prod%=Mod
            iprod*=root[i + 3]; iprod%=Mod

        self.root=root; self.iroot=iroot
        self.rate2=rate2; self.irate2=irate2
        self.rate3=rate3; self.irate3=irate3

    def add(self, A: list[int] | int, B: list[int] | int) -> list[int]:
        """ 必要ならば末尾に元を追加して, [A[i] + B[i]] を求める.

        """

        if type(A) == list:
            pass
        elif type(A) == int:
            A = [A]
        else:
            raise NotImplementedError

        if type(B) == list:
            pass
        elif type(B) == int:
            B = [B]
        else:
            raise NotImplementedError

        m = min(len(A), len(B))
        C = [(A[i] + B[i]) %Mod for i in range(m)]
        C.extend(A[m:])
        C.extend(B[m:])
        return C

    def sub(self, A: list[int] | int, B: list[int] | int) -> list[int]:
        """ 必要ならば末尾に元を追加して, [A[i] - B[i]] を求める.

        """

        if type(A) == list:
            pass
        elif type(A) == int:
            A = [A]
        else:
            raise NotImplementedError

        if type(B) == list:
            pass
        elif type(B) == int:
            B = [B]
        else:
            raise NotImplementedError

        m = min(len(A), len(B))
        C = [(A[i] - B[i]) % Mod for i in range(m)]
        C.extend(A[m:])
        C.extend([-b % Mod for b in B[m:]])
        return C

    def times(self, A: list[int], k: int) -> list[int]:
        """ [k * A[i]] を求める.

        """
        return [k * a % Mod for a in A]

    #参考元 https://judge.yosupo.jp/submission/72676
    def ntt(self, A: list[int]):
        """ A に Mod を法とする数論変換を施す

        ※ Mod はグローバル変数から指定

        References:
        https://github.com/atcoder/ac-library/blob/master/atcoder/convolution.hpp
        https://judge.yosupo.jp/submission/72676
        """

        N=len(A)
        H=(N-1).bit_length()
        l=0

        I=self.root[2]
        rate2=self.rate2; rate3=self.rate3

        while l<H:
            if H-l==1:
                p=1<<(H-l-1)
                rot=1
                for s in range(1<<l):
                    offset=s<<(H-l)
                    for i in range(p):
                        x=A[i+offset]; y=A[i+offset+p]*rot%Mod
                        A[i+offset]=(x+y)%Mod
                        A[i+offset+p]=(x-y)%Mod

                    if s+1!=1<<l:
                        rot*=rate2[(~s&-~s).bit_length()-1]
                        rot%=Mod
                l+=1
            else:
                p=1<<(H-l-2)
                rot=1
                for s in range(1<<l):
                    rot2=rot*rot%Mod
                    rot3=rot2*rot%Mod
                    offset=s<<(H-l)
                    for i in range(p):
                        a0=A[i+offset]
                        a1=A[i+offset+p]*rot
                        a2=A[i+offset+2*p]*rot2
                        a3=A[i+offset+3*p]*rot3

                        alpha=(a1-a3)%Mod*I

                        A[i+offset]=(a0+a2+a1+a3)%Mod
                        A[i+offset+p]=(a0+a2-a1-a3)%Mod
                        A[i+offset+2*p]=(a0-a2+alpha)%Mod
                        A[i+offset+3*p]=(a0-a2-alpha)%Mod

                    if s+1!=1<<l:
                        rot*=rate3[(~s&-~s).bit_length()-1]
                        rot%=Mod
                l+=2

    #参考元 https://judge.yosupo.jp/submission/72676
    def inverse_ntt(self, A):
        """ A を Mod を法とする逆数論変換を施す

        ※ Mod はグローバル変数から指定

        References:
        https://github.com/atcoder/ac-library/blob/master/atcoder/convolution.hpp
        https://judge.yosupo.jp/submission/72676
        """
        N=len(A)
        H=(N-1).bit_length()
        l=H

        J=self.iroot[2]
        irate2=self.rate2; irate3=self.irate3

        while l:
            if l==1:
                p=1<<(H-l)
                irot=1
                for s in range(1<<(l-1)):
                    offset=s<<(H-l+1)
                    for i in range(p):
                        x=A[i+offset]; y=A[i+offset+p]
                        A[i+offset]=(x+y)%Mod
                        A[i+offset+p]=(x-y)*irot%Mod

                    if s+1!=1<<(l-1):
                        irot*=irate2[(~s&-~s).bit_length()-1]
                        irot%=Mod
                l-=1
            else:
                p=1<<(H-l)
                irot=1
                for s in range(1<<(l-2)):
                    irot2=irot*irot%Mod
                    irot3=irot2*irot%Mod
                    offset=s<<(H-l+2)
                    for i in range(p):
                        a0=A[i+offset]
                        a1=A[i+offset+p]
                        a2=A[i+offset+2*p]
                        a3=A[i+offset+3*p]

                        beta=(a2-a3)*J%Mod

                        A[i+offset]=(a0+a1+a2+a3)%Mod
                        A[i+offset+p]=(a0-a1+beta)*irot%Mod
                        A[i+offset+2*p]=(a0+a1-a2-a3)*irot2%Mod
                        A[i+offset+3*p]=(a0-a1-beta)*irot3%Mod

                    if s+1!=1<<(l-2):
                        irot*=irate3[(~s&-~s).bit_length()-1]
                        irot%=Mod
                l-=2
        N_inv=pow(N, -1, Mod)
        for i in range(N):
            A[i]=N_inv*A[i]%Mod

    def non_zero_count(self, A: list[int]) -> int:
        """ A にある非零要素の個数を求める.

        Args:
            A (list[int]):

        Returns:
            int: 非零要素の個数
        """
        return len(A) - A.count(0)

    def is_sparse(self, A: list[int], threshold: int = 25) -> bool:
        """A が疎かどうかを判定する.

        Args:
            A (list[int]):
            threshold (int, optional): 非零要素の個数が threshold 以下ならば疎と判定する. Defaults to 25.

        Returns:
            bool: 疎?
        """

        return self.non_zero_count(A) <= threshold

    def coefficients_list(self, A: list[int]) -> tuple[list[int], list[int]]:
        """ A にある非零要素のリストを求める.

        Args:
            A (list[int]):

        Returns:
            tuple[list[int], list[int]]: ([d[0], ..., d[k-1]], [f[0], ..., f[k-1]]) の形のリスト.
                j = 0, 1, ..., k - 1 に対して, a[d[j]] = f[j] であることを意味する.
        """

        f = []; d = []
        for i in range(len(A)):
            if A[i] == 0:
                continue

            d.append(i)
            f.append(A[i])
        return d, f

    def convoluton_greedy(self, A: list[int], B: list[int]) -> list[int]:
        """ 畳み込み積 A * B を愚直な方法で求める.

        Args:
            A (list[int]):
            B (list[int]):

        Returns:
            list[int]: 畳み込み積 A * B
        """

        if len(A) < len(B):
            A, B = B, A

        n = len(A)
        m = len(B)
        C = [0] * (n + m - 1)
        for i in range(n):
            for j in range(m):
                C[i + j] += A[i] * B[j] % Mod

        for k in range(n + m - 1):
            C[k] %= Mod

        return C

    def convolution(self, A: list[int], B: list[int]) -> list[int]:
        """ 畳み込み積 A * B を求める.

        Args:
            A (list[int]):
            B (list[int]):

        Returns:
            list[int]: 畳み込み積 A * B
        """

        if (not A) or (not B):
            return []

        N=len(A)
        M=len(B)
        L=M+N-1

        if min(N,M)<=50:
            return self.convoluton_greedy(A, B)

        H=L.bit_length()
        K=1<<H

        A=A+[0]*(K-N)
        B=B+[0]*(K-M)

        self.ntt(A)
        self.ntt(B)

        for i in range(K):
            A[i]=A[i]*B[i]%Mod

        self.inverse_ntt(A)

        return A[:L]

    def autocorrelation(self, A: list[int]) -> list[int]:
        """ 自分自身との畳み込み積を求める.

        Args:
            A (list[int]):

        Returns:
            list[int]: 畳み込み積 A * A
        """

        N=len(A)
        L=2*N-1

        if N<=50:
            C=[0]*L
            for i in range(N):
                for j in range(N):
                    C[i+j]+=A[i]*A[j]
                    C[i+j]%=Mod
            return C

        H=L.bit_length()
        K=1<<H

        A=A+[0]*(K-N)

        self.ntt(A)

        for i in range(K):
            A[i]=A[i]*A[i]%Mod
        self.inverse_ntt(A)

        return A[:L]

    def multiple_convolution(self, *A: list[int]) -> list[int]:
        """ A = (A[0], A[1], ..., A[k - 1]) に対して, この k 個の畳み込み積 A[0] * A[1] * ... * A[k - 1] を求める.

        Args:
            A (list[list[int]]): 畳み込む k 個の整数のリスト

        Returns:
            list[int]: k 個の畳み込み積 A[0] * A[1] * ... * A[k - 1]
        """

        from collections import deque

        if not A:
            return [1]

        Q=deque(list(range(len(A))))
        A=list(A)

        while len(Q)>=2:
            i=Q.popleft(); j=Q.popleft()
            A[i]=self.convolution(A[i], A[j])
            A[j]=None
            Q.append(i)

        i=Q.popleft()
        return A[i]

    def inverse(self, F: list[int], length: int = None) -> list[int]:
        """ F * G = [1, 0, 0, ..., 0] (0 が (length - 1) 個) を満たす長さ length のリスト G を求める.

        Args:
            F (list[int]):
            length (int, optional): 求める G の長さ. None のときは length = len(F) とする. Defaults to None.

        Returns:
            list[int]: _description_
        """

        M = len(F) if length is None else length

        if M <= 0:
            return []

        if self.is_sparse(F):
            # 愚直に漸化式を用いて求める.
            # 計算量: F にある係数が非零の項の個数を K, 求める最大次数を N として, O(NK) 時間

            d,f=self.coefficients_list(F)

            G=[0]*M
            alpha=pow(F[0], -1, Mod)
            G[0]=alpha

            for i in range(1, M):
                for j in range(1, len(d)):
                    if d[j]<=i:
                        G[i]+=f[j]*G[i-d[j]]%Mod
                    else:
                        break

                G[i]%=Mod
                G[i]=(-alpha*G[i])%Mod
            del G[M:]
        else:
            # FFTの理論を応用して求める.
            # 計算量: 求めたい項の個数をNとして, O(N log N)
            # Reference: https://judge.yosupo.jp/submission/42413

            N=len(F)
            r=pow(F[0], -1, Mod)

            m=1
            G=[r]
            while m<M:
                A=F[:min(N, 2*m)]; A+=[0]*(2*m-len(A))
                B=G.copy(); B+=[0]*(2*m-len(B))

                Calc.ntt(A); Calc.ntt(B)
                for i in range(2*m):
                    A[i]=A[i]*B[i]%Mod

                Calc.inverse_ntt(A)
                A=A[m:]+[0]*m
                Calc.ntt(A)
                for i in range(2*m):
                    A[i]=-A[i]*B[i]%Mod
                Calc.inverse_ntt(A)

                G.extend(A[:m])
                m<<=1
            G=G[:M]
        return G

    def flood_div(self, F: list[int], G: list[int]) -> list[int]:
        assert F[-1]
        assert G[-1]

        F_deg=len(F)-1
        G_deg=len(G)-1

        if F_deg<G_deg:
            return []

        m=F_deg-G_deg+1
        return self.convolution(F[::-1], Calc.inverse(G[::-1],m))[m-1::-1]

    def mod(self, F: list[int], G: list[int]) -> list[int]:
        while F and F[-1] == 0:
            F.pop()

        while G and G[-1] == 0:
            G.pop()

        if not F:
            return []

        return Calc.sub(F, Calc.convolution(Calc.flood_div(F, G), G))

#==================================================
"""
Note
[1] RMQ(区間上の最小値:Range Minimum Query)
op=lambda x,y:min(x,y)
unit=float("inf")
act=lambda alpha,x:alpha
comp=lambda alpha,beta:alpha
"""
from typing import TypeVar, Callable, Generic

M = TypeVar('M')
F = TypeVar('F')
class Lazy_Evaluation_Tree(Generic[M, F]):
    def __init__(self, L: list[M], op: Callable[[M, M], M], unit: M, act: Callable[[F, M], M], comp: Callable[[F, F], F], id: F):
        """ op を演算, act を作用とする L を初期状態とする遅延セグメント木を作成する.

        [条件]
        M: Monoid, F={f: F x M→ M: 作用素} に対して, 以下が成立する.
        F は恒等写像 id を含む.つまり, 任意の x in M に対して id(x)=x
        F は写像の合成に閉じている. つまり, 任意の f,g in F に対して, comp(f,g) in F
        任意の f in F, x,y in M に対して, f(xy)=f(x) f(y) である.

        [注意]
        作用素は左から掛ける. 更新も左から.

        Args:
            L (list[M]): 初期状態
            op (Callable[[M, M], M]): M の演算
            unit (M): M の単位元
            act (Callable[[F, M], M]): F から M への作用
            comp (Callable[[F, F], F]): F 同士の合成
            id (F): F の単位元
        """

        self.op = op
        self.unit = unit
        self.act = act
        self.comp = comp
        self.id = id

        N = len(L)
        d = max(1, (N - 1).bit_length())
        k = 1 << d

        self.data = data = [unit] * k + L + [unit] * (k - len(L))
        self.lazy = [id] * (2 * k)
        self.N = k
        self.depth = d

        for i in range(k - 1, 0, -1):
            data[i] = op(data[i << 1], data[i << 1 | 1])

    def _eval_at(self, m: int) -> None:
        return self.data[m] if self.lazy[m] == self.id else self.act(self.lazy[m], self.data[m])

    #配列の第m要素を下に伝搬
    def _propagate_at(self, m: int) -> None:
        self.data[m] = self._eval_at(m)
        lazy = self.lazy; comp = self.comp

        if m < self.N and self.lazy[m] != self.id:
            lazy[m << 1] = comp(lazy[m], lazy[m << 1])
            lazy[m << 1 | 1] = comp(lazy[m], lazy[m << 1 | 1])

        lazy[m] = self.id

    #配列の第m要素より上を全て伝搬
    def _propagate_above(self, m: int) -> None:
        for h in range(m.bit_length() - 1, 0, -1):
            self._propagate_at(m >> h)

    #配列の第m要素より上を全て再計算
    def _recalc_above(self, m: int) -> None:
        data = self.data; op = self.op
        eval_at = self._eval_at
        while m > 1:
            m >>= 1
            data[m] = op(eval_at(m << 1), eval_at(m << 1 | 1))

    def get(self, k: int) -> M:
        """ 第 k 要素を取得する

        Args:
            k (int): 要素の場所

        Returns:
            M: 第 k 要素
        """
        m = k + self.N
        self._propagate_above(m)
        self.data[m] = self._eval_at(m)
        self.lazy[m] = self.id
        return self.data[m]

    #作用
    def action(self, l: int, r: int, alpha: F, left_closed: bool = True, right_closed: bool = True) -> None:
        """ 第 l 要素から第 r 要素まで全てに alpha を作用させる

        Args:
            l (int): 左端
            r (int): 右端
            alpha (F): 作用させる値
            left_closed (bool, optional): False にすると, 左端が開区間になる. Defaults to True.
            right_closed (bool, optional): False にすると, 右端が開区間になる. Defaults to True.
        """

        L = l + self.N + (not left_closed)
        R = r + self.N + right_closed

        L0 = R0 = -1
        X, Y = L, R- 1
        while X < Y:
            if X & 1:
                L0 = max(L0, X)
                X += 1

            if Y & 1 == 0:
                R0 = max(R0, Y)
                Y -= 1

            X >>= 1
            Y >>= 1

        L0 = max(L0, X)
        R0 = max(R0, Y)

        self._propagate_above(L0)
        self._propagate_above(R0)

        lazy = self.lazy; comp = self.comp
        while L < R:
            if L & 1:
                lazy[L] = comp(alpha, lazy[L])
                L += 1

            if R & 1:
                R -= 1
                lazy[R] = comp(alpha, lazy[R])

            L >>= 1
            R >>= 1

        self._recalc_above(L0)
        self._recalc_above(R0)

    def update(self, k: int, x: M) -> None:
        """ 第 k 要素を x に更新する.

        Args:
            k (int): 要素の場所
            x (M): 変更後の第 k 要素
        """

        m = k+self.N
        self._propagate_above(m)
        self.data[m] = x
        self.lazy[m] = self.id
        self._recalc_above(m)

    def product(self, l: int, r: int, left_closed: bool = True, right_closed: bool = True) -> M:
        """ 第 l 要素から第 r 要素までの総積を求める.

        Args:
            l (int): 左端
            r (int): 右端
            left_closed (bool, optional): False にすると, 左端が開区間になる. Defaults to True.
            right_closed (bool, optional): False にすると, 右端が開区間になる. Defaults to True.

        Returns:
            M: 総積
        """

        L = l + self.N + (not left_closed)
        R = r + self.N + right_closed

        L0 = R0 = -1
        X, Y = L, R - 1
        while X < Y:
            if X & 1:
                L0 = max(L0, X)
                X += 1

            if Y & 1 == 0:
                R0 = max(R0, Y)
                Y -= 1

            X >>= 1
            Y >>= 1

        L0 = max(L0, X)
        R0 = max(R0, Y)

        self._propagate_above(L0)
        self._propagate_above(R0)

        vL = vR = self.unit
        op = self.op; eval_at = self._eval_at
        while L < R:
            if L & 1:
                vL = op(vL, eval_at(L))
                L += 1

            if R & 1:
                R -= 1
                vR = op(eval_at(R), vR)

            L >>= 1
            R >>= 1

        return self.op(vL, vR)

    def all_product(self) -> M:
        """ この遅延セグメント木が持っている要素に関する総積を求める.

        Returns:
            M: 総積
        """

        return self.product(0, self.N - 1)

    def max_right(self, left: int, cond: Callable[[int], bool]) -> int:
        """ 以下の2つをともに満たす r の1つを返す.\n
        (1) r = left or cond(data[left] * data[left + 1] * ... * data[r - 1]): True
        (2) r = N or cond(data[left] * data[left + 1] * ... * data[r]): False
        ※ cond が単調減少の時, cond(data[left] * ... * data[r - 1]): True を満たす最大の r となる.

        Args:
            left (int): 左端
            cond: 条件式 (cond(unit) = True を要求)

        Returns:
            int: 条件を満たす r.
        """

        assert 0 <= left <= self.N
        assert cond(self.unit)

        if left == self.N:
            return self.N

        left += self.N

    def max_right(self, left: int, cond) -> int:
        """ 以下の (1), (2) を満たす整数 r を求める.
        (1) r=left or cond(data[left] data[left+1] ... data[r-1]): True
        (2) r=N or cond(data[left] data[left+1] ... data[r]): False

        Args:
            left (int): 左端
            cond : 条件

        Returns:
            int: (1), (2) を満たす整数 r
        """

        assert 0 <= left <= self.N, f"添字 ({left = }) が範囲外"
        assert cond(self.unit), "単位元が条件を満たさない"

        if left == self.N:
            return self.N

        left += self.N
        sm = self.unit

        op = self.op; data = self.data
        first = True

        self._propagate_above(left)

        while first or (left & (-left)) != left:
            first = False
            while left % 2 == 0:
                left >>= 1

            if not cond(op(sm, self._eval_at(left))):
                while left < self.N:
                    self._propagate_at(left)
                    left <<= 1
                    self._propagate_at(left)
                    if cond(op(sm, data[left])):
                        sm = op(sm, data[left])
                        left += 1
                return left - self.N
            sm = op(sm, self._eval_at(left))
            left += 1

        return self.N

    #リフレッシュ
    def refresh(self) -> None:
        """ 遅延セグメント木の遅延情報をリセットする.
        """

        lazy = self.lazy; comp = self.comp
        for m in range(1, 2 * self.N):
            self.data[m] = self._eval_at(m)

            if m < self.N and self.lazy[m] != self.id:
                lazy[m << 1] = comp(lazy[m], lazy[m << 1])
                lazy[m << 1 | 1] = comp(lazy[m], lazy[m << 1 | 1])
            lazy[m] = self.id

    def __getitem__(self, k: int) -> M:
        return self.get(k)

    def __setitem__(self, k: int, x: M) -> None:
        self.update(k, x)

#==================================================
from operator import add
def encode(x0: int, x1: int) -> int:
    return 1_000_000_000 * x0 + x1

def decode(y: int) -> tuple[int, int]:
    return divmod(y, 1_000_000_000)

def act_1(a: int, x: int) -> int:
    x0, x1 = decode(x)
    return x if a % 2 == 0 else encode(x1, x0)

def act_2(a: int, y: int) -> int:
    y0, y1 = decode(y)
    return encode(y0 + a * y1, y1)

def solve():
    N, Q = map(int, input().split())
    S = list(f"*{input().strip()}")
    S[-1] = "B"
    W = list(map(int, input().split()))

    X = Lazy_Evaluation_Tree[tuple[int, int], int](
        [encode(1, 0) if S[i] in { "G", "*" } else encode(0, 1) for i in range(N + 1)],
        add,
        encode(0, 0),
        act_1,
        add,
        0
    )

    W = Lazy_Evaluation_Tree[tuple[int, int], int](
        [encode(w, 1) for w in W],
        add,
        encode(0, 0),
        act_2,
        add,
        0
    )

    def latest_backed_at(v: int) -> int:
        alpha = decode(X.product(1, v - 1))
        if alpha[1] == 0:
            return 0

        return X.max_right(1, lambda z: decode(z)[1] < alpha[1])

    def next_back_at(v: int) -> int:
        beta = decode(X.product(1, v - 1))
        return min(X.max_right(1, lambda z: decode(z)[1] <= beta[1]), N)

    ans = []
    for q in range(Q):
        mode, *option = map(int, input().split())
        if mode == 1:
            l, r = option
            if r == N:
                r -= 1

            X.action(l, r, 1)
        elif mode == 2:
            l, r, a = option
            W.action(l, r, a)
        elif mode == 3:
            v, K = option
            U = list(map(int, input().split()))

            # U 以降 (U 含める) で最初の Back になる r を求める.
            r = latest_backed_at(v)

            back_time: defaultdict[int, int] = defaultdict(int)
            less = 0
            for u in U:
                # v より前の頂点は, 絶対に子孫にならないので, SKIP
                if u < v:
                    less += 1
                    continue

                t = latest_backed_at(u)
                back_time[t] += 1

            vr = next_back_at(v)
            p = decode(W.product(v, vr))[0] * pow(decode(W.product(0, vr))[0], -1, Mod) % Mod
            polys = []

            # 確定要素
            poly = [1 if s == back_time[r] else 0 for s in range(back_time[r] + 1)] + [0] * less
            polys.append(poly)

            for t, d in back_time.items():
                if t == r:
                    continue

                poly = [0] * (d + 1)
                poly[0] += 1 - p
                poly[d] += p

                polys.append(poly)

            P = Calc.multiple_convolution(*polys)
            ans.append(P)

    return ans

#==================================================
import sys
input = sys.stdin.readline
write = sys.stdout.write

from collections import defaultdict

Mod = 998244353
Calc = Calculator()

to_string = lambda P: " ".join(map(str, P))
write("\n".join(map(to_string, solve())))