池塘上有 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 取模的结果。

对于所有数据，保证 1\le n\le 2\times 10^5，0\le q\le 2\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。

梦熊