Description

烟花在夜空中绽放连成一片，我们把这些连成一片的烟花看成一棵含有 $n$ 个点的有根树，根为最早点燃的烟花 $1$。

烟花有红蓝两种颜色，为了方便，我们对这棵树黑白染色。最初有 $p$ 个限制，一条限制形如 $(x_i,y_i)$，表示树中编号为 $x_i$ 的点的子树中黑点只能恰好有 $y_i$ 个。当年，他们认为满足其子树内所有有限制点的限制的子树是均好的子树。显然，要想使一个子树成为均好的子树，可能有多种染色方法。

你需要回答以下两种询问：

• Z k c，表示给点 $k$ 以均等概率在 $[0,c]$ 中选择一个数 $f$，然后给点 $k$ 直接加上 $f$ 个没有限制的儿子，其它儿子状态不变。问点 $k$ 为根的子树成为均好的子树的期望染色方法数量。
• H k，表示如果去掉 $k$ 的所有有限制儿子的限制，询问 $k$ 为根的子树成为均好的子树的染色方法数量。

我们并没有必要点燃更多的烟花，因此所有的询问都是相互独立的，没有询问会真的影响原树。

我们深知可能复现不了当时完整的情况，历史太过斑驳，可能的烟花组合成千上万，因此你只需要得到答案对 $998244353$ 这个大质数取模的值。

Input Format

第一行两个整数 $n,p$，表示树的节点个数与限制个数。

接下来 $n-1$ 行，每行两个数 $u,v$，表示 $u,v$ 之间有一条直连边。这 $n-1$ 行表示树的结构。

接下来 $p$ 行，每行两个数 $(x_i,y_i)$，表示限制以 $x_i$ 点为根的子树，需要恰好存在 $y_i$ 个黑点在其子树内。

接下来一行一个整数 $q$，表示询问个数。

接下来 $q$ 行，每行一个字符另加 $1$ 或 $2$ 个整数表示题目中说明的询问。

Output Format

为了减小输出量，我们假设第 $i$ 个询问（$i$ 从 $1$ 开始）的答案为 $ans_i$，你只需要输出一行，表示所有询问的 $i\times ans_i$ 的异或和。最终的异或和以及每一个 $i\times ans_i$ 都无需对 $998244353$ 取模，但每个询问的答案 $ans_i$ 是对其取模后的答案。

注意：std 不依赖于输出方式。也就是说，std 可以独立获取每一个询问的答案。

14 5
1 2
1 3
4 1
5 2
2 6
3 7
3 8
9 4
12 6
11 6
6 10
8 13
14 8
2 3
10 0
7 1
13 1
14 0
10
Z 2 5
H 14
Z 7 3
Z 7 1
H 6
Z 1 9
H 1
H 8
H 12
Z 10 1

665340330

Hint

样例解释

如图为样例 #1 的烟花，构成一个有 $14$ 个点，其中 $5$ 个限制点的树。与题目中不同的是，我们用红色烟花表示限制点，蓝色烟花表示无限制点。红色烟花右上角的浅蓝色数字表示其限制的黑点数量。

初始情况下每一个点为根子树的合法烟花燃放方法数量如下（从左至右第 $i$ 项表示以第 $i$ 个点为根的子树的答案）：

下面我们给出询问的答案与部分解释：

• Z 2 5，为 $2$ 号点添加 $i$ 个儿子后的 $2$ 号点子树内合法烟花燃放数量表示为此数列的第 $i+1$ 项：$[10,20,35,56,84,120]$。总期望即为 $\frac{325}{6}$。对 $998244353$ 取模之后得到 $166374113$。
• H 14，由于 $14$ 号点没有儿子，因此答案仍然为 $1$。
• Z 7 3，共有 $10$ 种可能的合法烟花燃放方案，总期望即为 $\frac{5}{2}$，对 $998244353$ 取模之后得到 $499122179$。
• Z 7 1 的答案为 $499122178$。
• H 6 的答案为 $16$。
• Z 1 9 的答案为 $32736$。
• H 1，去除 $1$ 的所有有限制儿子（仅有节点 $2$）的限制后有 $1024$ 种可能的合法烟花燃放方案。
• H 8 的答案为 $8$。
• H 12 没有儿子，因此答案不变，此询问的答案仍然为 $2$。
• Z 10 1 的答案为 $1$。

最终，所有询问的 $i\times ans_i$ 的异或和即为 $665340330$。

数据范围

请注意常数因子对程序效率的影响。

本题采用捆绑测试与子任务依赖。

下面定义 $S=3\times 10^5$。

特殊性质 $A$：$p=0$。

特殊性质 $B$：满足不存在 Z 询问。

对于 $100\%$ 的数据，存在输入的所有数均为 $\leqslant S$ 的整数。特别地，存在 $0\leqslant p\leqslant n$，输入的任何树的节点编号 $x$ 都满足 $1\leqslant x \leqslant n$。保证输入的询问字符都为 Z 或 H，输入的一定是一棵树。保证对于所有限制存在 $x_i\neq x_j(i\neq j)$。

冬天的最后一场雪如约而至，很快又要迎来一个新的春天。万物都在等待复苏，可峰城里的一个小巷子，再也不复往日繁荣。

八十多年过去，我们早已找不到当初的巷子，只留下这样一个故事。

感谢你放的烟花。