アルファベット $\{a, b, c, d, e, f\}$ 上の長さ $n$ の文字列 $s$ が与えられます。この文字列に対して $q$ 回の操作を行います。各操作は、文字列内のちょうど1文字を別の文字に置き換えるものです。

文字列 $s$ のすべての部分文字列（$s$ からいくつかの文字を取り除いて得られる文字列）からなる多重集合を $X_s$ とします。 あなたのタスクは、$X_s$ 内に少なくとも2回出現するような異なる空でない文字列 $t$ の個数を管理することです。

例えば、文字列 ababa においては、そのような文字列 $t$ は6つ存在します。 文字 a は $X_s$ 内に3回出現します。 文字 b は $X_s$ 内に2回出現します。 文字列 ab は $X_s$ 内に3回出現します（$s$ から位置 3, 4, 5; 2, 3, 5; または 1, 2, 5 の文字を取り除いた場合）。 文字列 ba は $X_s$ 内に3回出現します（$s$ から位置 1, 4, 5; 1, 3, 4; または 1, 2, 3 の文字を取り除いた場合）。 文字列 aa は $X_s$ 内に3回出現します（$s$ から位置 2, 4, 5; 2, 3, 4; または 1, 2, 4 の文字を取り除いた場合）。 文字列 aba は $X_s$ 内に4回出現します（$s$ から位置 4, 5; 3, 4; 2, 3; または 1, 2 の文字を取り除いた場合）。

初期状態の文字列 $s$ および各操作後の文字列 $s$ について、このような文字列 $t$ の個数を計算してください。 これらの数は非常に大きくなる可能性があるため、998 244 353 で割った余りを出力してください。

入力

入力の1行目には、2つの整数 $n$ と $q$ ($3 \le n \le 50\,000, 0 \le q \le 50\,000$) が与えられます。ここで $n$ は文字列の長さ、$q$ は操作の回数を表します。 2行目には、英小文字からなる長さ $n$ の文字列が与えられます。この文字列は a から f までの文字のみで構成されます。 続く $q$ 行には操作の内容が記述されています。各操作は整数 $p_i$ ($1 \le p_i \le n$) と文字 $z_i$ ($z_i \in \{a, b, c, d, e, f\}$) からなり、文字列 $s$ の $p_i$ 番目の文字を $z_i$ に置き換えることを意味します。

出力

出力は $q + 1$ 行からなる必要があります。$i$ 行目には、文字列 $s$ の部分文字列として少なくとも2回出現する異なる文字列 $t$ の個数を表す整数を1つ出力してください。すべての結果は 998 244 353 を法として出力してください。

入出力例

入力 1

4 3
abca
1 a
4 d
2 c

出力 1

1
1
0
4

注記

例の解説：各更新後の文字列 $s$ の状態と、$s$ の部分文字列として少なくとも2回出現する文字列 $t$ は以下の通りです。 文字列: abca、部分文字列: {a} 文字列: abca、部分文字列: {a} 文字列: abcd、部分文字列: {} 文字列: accd、部分文字列: {ac, acd, cd, c}

小課題

ある程度の点数が割り当てられたテストケースでは、元の文字列およびすべての操作において a と b の文字のみが使用されます。