题目描述

池塘上有 $n$ 片荷叶，从 $1$ 编号到 $n$。现在有一棵大小为 $n$ 的有根树 $T$ 描述了这些荷叶的关系。$T$ 的根是 $1$。

每片荷叶上都有一个符号 $\texttt{U}$ 或者 $\texttt{D}$。这个符号表示如果青蛙在第 $i$ 片荷叶上，则：

• 若符号是 $\texttt{U}$，则可以跳到 $T$ 上 $i$ 的祖先（不包含自身）。
• 若符号是 $\texttt{D}$，则可以跳到 $T$ 上 $i$ 的子孙（不包含自身）。

定义这棵树对青蛙是友好的，当且仅当青蛙可以从任意一个荷叶 $s$ 开始，跳过所有荷叶至少一次，回到 $s$。

由于一些原因，一些荷叶上的符号模糊了，记为 $\texttt{?}$ 符号。定义 $f(T)$ 为把每个 $\texttt{?}$ 符号替换成 $\texttt{U}$ 或 $\texttt{D}$ 后，这棵树对青蛙是友好的方案数。

由于一些原因，这些荷叶上的三种符号可能会发生局部变化，有 $q$ 次修改，每次修改让第 $x$ 片荷叶的符号变成 $y$，你需要在每次修改后和初始时求出 $f(T)$ 对 $998244353$ 取模的结果。

输入格式

第一行包含两个整数 $n,q$。

第二行包含一个长度为 $n$ 的字符串，第 $i$ 个字符表示第 $i$ 片荷叶上的符号 $a_i$。

接下来 $n-1$ 行，第 $i$ 行两个整数 $u_i,v_i$，表示树 $T$ 上存在一条 $u_i$ 到 $v_i$ 的边。

接下来 $q$ 行，第 $i$ 行一个整数和一个字符 $x_i,y_i$，表示让第 $x_i$ 片荷叶的符号变成 $y_i$。

输出格式

包含 $q+1$ 行，第 $i$ 行包含一个整数，表示前 $i-1$ 次修改按顺序执行完后，$f(T)$ 对 $998244353$ 取模的结果。

5 3
?????
1 2
1 3
2 4
3 5
1 U
1 D
4 U

4
0
4
4

提示

特殊性质 A：保证 $a_i,y_i\in \{\texttt{U},\texttt{D}\}$。

特殊性质 B：保证 $q=0$，且 $a_i=\texttt{?}$。

对于所有数据，保证 $1\le n\le 3\times 10^5$，$0\le q\le 3\times 10^5$。

保证 $1\le u_i,v_i\le n$，给定的边构成一棵以 $1$ 为根的树。

保证 $a_i,y_i\in \{\texttt{U},\texttt{D},\texttt{?}\}$。保证 $1\le x_i\le n$。