Notice (2026/01/24)

It has been confirmed that the values computed by the Writer's and Testers' solutions for this problem are not the values that should have been computed.

Therefore, this problem is regarded as a flawed problem.

We apologize for this.

Problem Visual

Problem Statement

You are given a positive integer $N$ and the following.

• A string $S$ of length $N$ consisting of G and B, with indices starting from $1$.
• A sequence $W$ of non-negative integers of length $(N+1)$, with indices starting from $0$.

You are given $Q$ queries. Each query is one of the following $3$ types.

• Type I: Integers $l, r~(1 \leq l \leq r \leq N)$ are given. Swap G and B in the $l$-th through $r$-th characters of $S$. Formally, for every integer $i$ satisfying $l \leq i \leq r$, operate on $S$ as follows, $1$ time each.
  • If the $i$-th character of $S$ is G, change the $i$-th character of $S$ to B.
  • If the $i$-th character of $S$ is B, change the $i$-th character of $S$ to G.
• Type II: Integers $l, r~(0 \leq l \leq r \leq N), a$ are given. Add $a$ to each of the $(r-l+1)$ integers $W_l, \dots, W_r$. It is guaranteed that the following hold after this query is executed.
  • $W_l, \dots, W_r$ are all non-negative integers.
  • $W_0 > 0$.
  • $\sum_{i=0}^N W_i < 998244353$.
• Type III: An integer $K$ and $(K+1)$ integers $v, u_1, \dots, u_K$ are given over 2 lines. Using $N, S, W$ at the time this query is given and $K, v, u_1, \dots, u_K$ given in the query, answer the problem Go or Back!! defined below.

  Go or Back!!

  There is an undirected graph $G$. Initially, this $G$ has $1$ vertex and $0$ edges. We call this only vertex vertex $0$. Cherry-chan is initially at vertex $0$.

  Cherry-chan will now perform $N$ actions. The $i~(1 \leq i \leq N)$-th action consists of the following, performed in the order (1), (2). Here, $S_i$ denotes the $i$-th character of $S$.

  • (1) Let $x$ be the number of the vertex where Cherry-chan is currently located. Add $1$ vertex, vertex $i$, to $G$. Then, add $1$ undirected edge connecting vertex $x$ and vertex $i$ to $G$.
  • (2) Act according to $S_i$ as follows.
    • If $S_i = $ G, move to vertex $i$.
    • If $S_i = $ B, move to vertex $i$. Then, choose an integer $j$ from the $(i+1)$ integers between $0$ and $i$, inclusive, with probability proportional to $W_j$, and move to vertex $j$ for the chosen $j$.
      • Formally, the probability that $j$ is chosen as an integer between $0$ and $i$, inclusive, is $\dfrac{W_j}{W_0 + W_1 + \dots + W_i}$.

  Here, the vertex choices in the case $S_i =$ B of (2) are independent.

  It is guaranteed that $G$ after Cherry-chan finishes the $N$ actions is a tree with $(N+1)$ vertices.

  For each of $k = 0, 1, 2, \dots, K$, let $P_k$ be the probability that the following holds, and find $P_k \pmod{998244353}$.

  • When $G$ is regarded as a rooted tree with root vertex $0$, exactly $k$ of the $K$ vertices $u_1, \dots, u_K$ are descendants of vertex $v$ (vertex $v$ itself is considered a descendant of vertex $v$).

Notes

Under the constraints of this problem, it can be proved that for each $P_k$ in the answer to Go or Back!!, there exists a pair of integers $(\alpha, \beta)$ satisfying the following.

• $\beta$ is not a multiple of $998244353$.
• $\beta \times P_k = \alpha$.

For a pair of integers $(\alpha, \beta)$ satisfying these conditions, there exists a unique integer $\gamma$ between $0$ and less than $998244353$ such that $$\beta \times \gamma \equiv \alpha \pmod{998244353}$$ Using this integer $\gamma$, we define $P_k \pmod{998244353} := \gamma$.

Although there are many possible pairs of integers $(\alpha, \beta)$ satisfying the conditions, it can be proved that $\gamma$ does not depend on the choice of $\alpha, \beta$ and is determined by $P_k$ alone.

Constraints

• $1 \leq N \leq 2 \times 10^5$.
• $S$ is a string of length $N$ consisting of G and B.
• $0 \leq W_i \quad (0 \leq i \leq N)$.
• $W_0 > 0$.
• $\displaystyle \sum_{i=0}^N W_i < 998244353$.
• $1 \leq Q \leq 2 \times 10^5$.
• Properties of the queries
  • Type I
    • $1 \leq l \leq r \leq N$.
  • Type II
    • $0 \leq l \leq r \leq N$.
    • After this query is executed, the following hold.
      • $W_l, \dots, W_r$ are non-negative integers.
      • $W_0 > 0$.
      • $\sum_{i=0}^N W_i < 998244353$.
  • Type III
    • $0 \leq v \leq N$.
    • $1 \leq K \leq N + 1$.
    • $0 \leq u_1 < u_2 < \dots < u_K \leq N$.
• Constraints on test files
  • The sum of $K$ given in Type III is at most $4 \times 10^5$.
• All numbers given in the input are integers.

Input

The input is given from standard input in the following format.

$N$ $Q$
$S$
$W_0$ $W_1$ $\cdots$ $W_N$
$\textrm{Query}_1$
$\textrm{Query}_2$
$\vdots$
$\textrm{Query}_Q$

Each query $\textrm{Query}_q$ is given in the following format.

• Type I

  $1$ $l$ $r$

• Type II

  $2$ $l$ $r$ $a$

• Type III (note that the input spans $2$ lines!!)

  $3$ $v$ $K$
  $u_1$ $\dots$ $u_K$

Output

Let $Q_3$ be the number of Type III queries. The output consists of $Q_3$ lines.

On the $r~(1 \leq r \leq Q_3)$-th line, print $P_0 \pmod{998244353}, P_1 \pmod{998244353}, \dots, P_K \pmod{998244353}$ for the $r$-th Type III query, in this order, separated by spaces.

Do not forget the newline at the end.

Sample

5 4
GBBGG
7 2 5 3 4 6
3 1 3
2 3 5
2 1 2 -1
1 2 5
3 2 4
0 1 2 5

0 748683265 499122177 748683265
0 840626824 157617530 0 0

27 4
GBBBBBBBBBBBBBBBBGGGGBGGGGG
20240221 20050928 19970104 19981114 19980215 20010129 19990417 20000418 19991012 20021219 20020323 19981021 20010829 20020112 19991013 20010710 20000102 20020113 20060109 20040725 20050707 20050412 20030217 20061108 20060509 20040818 20050215 20050122
3 1 28
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
2 2 17 -200000
2 22 22 -200000
3 1 28
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

0 0 222988788 771769147 992116430 710638604 457685736 692110246 611753846 627562333 676906014 653592675 487428586 980604359 696548956 58536970 520775465 988181969 248027971 769018906 322625600 314143540 950198154 997357843 689168976 582264942 62212162 887691431 0
0 0 155273704 671270277 521295779 361253626 655040713 211805211 873728974 641978190 429760573 563027688 632727160 595596749 82203229 601652105 441511828 336327499 544567300 778057437 840394959 332445457 264024640 263262986 995391962 592085902 410020362 182472280 0