問題文

$1$ から $N$ までの番号が付いた $N$ 人が、番号順に一列に並んでいます。 各人は 「正直者」 または 「嘘つき」 のいずれかの種類に分類されます。
二択の質問をされたとき、正直者は必ず正しく答え、 嘘つきは必ず正しい答えと逆の答えをします。

人 $i$ は、次の質問に Yes または No で答えます。

人 $1,2,\ldots,i$ のうち、自分と同じ種類の人は過半数^†を占めていますか？

全員の回答結果を表す長さ $N$ の文字列 $S$ が与えられます。 $S_i=$ Y は人 $i$ の回答が Yes、 $S_i=$ N は No であることを表します。
文字列 $S$ に対して、$Q$ 個のクエリを順に処理してください^‡。 クエリには以下の $2$ 種類が存在します。

• 1 i： 人 $i$ の回答 $S_i$ を反転してください。 すなわち、$S_i=$ Y なら N に、 $S_i=$ N なら Y に変更してください。
• 2 K： 現在の $S$ に対して、 嘘つきがちょうど $K$ 人で、全員の回答が $S$ と一致するような各人の種類の割り当ての個数 を $998244353$ で割った余りで出力してください。

^† 「過半数」とは、全体の人数が $x$ 人であるときに、 $\left\lfloor \frac{x}{2} \right\rfloor + 1$ 人以上であることを意味します。
^‡ 各クエリは独立ではありません。 $1$ 種類目のクエリによる $S$ の変更は、それ以降のクエリにも引き継がれます。

制約

• $1 \leq N \leq 10^6$
• $1 \leq Q \leq 10^5$
• $S$ は Y と N からなる長さ $N$ の文字列
• $1$ 種類目のクエリでは、$1 \leq i \leq N$
• $2$ 種類目のクエリでは、$0 \leq K \leq N$
• $2$ 種類目のクエリが $1$ 個以上含まれる
• $N,Q,i,K$ は整数

入力

入力は以下の形式で標準入力から与えられます。

$N$ $Q$
$S$
$\mathrm{query}_1$
$\mathrm{query}_2$
$\vdots$
$\mathrm{query}_Q$

各クエリは、以下のいずれかの形式で与えられます。

1 $i$

2 $K$

出力

$2$ 種類目のクエリが与えられるたびに、そのクエリに対する答えを $998244353$ で割った余りで一行に出力してください。