{"raw_statement":[{"iden":"background","content":"回忆本身就是惩罚，惩罚那些不愿往前走的人，将他们困在那条小巷子里，怎么也走不出去。\n\n每一年都有烟花，唯独那一年的烟花最好看。\n\n“我要对烟花许愿，许我们永远在一起。”\n\n“就算不许愿，我们也会永远在一起的。”\n\n再后来，死了的人被葬在了那座山上，活着的人被记忆困在了那条巷中。今天的我们听到这个故事，只是想再放一次故事里的烟花，放给那些再没能陪身旁的人看到一次烟花的人。"},{"iden":"statement","content":"烟花在夜空中绽放连成一片，我们把这些连成一片的烟花看成一棵含有 $n$ 个点的有根树，根为最早点燃的烟花 $1$。\n\n烟花有红蓝两种颜色，为了方便，我们对这棵树黑白染色。最初有 $p$ 个限制，一条限制形如 $(x_i,y_i)$，表示树中编号为 $x_i$ 的点的子树中黑点只能**恰好**有 $y_i$ 个。当年，他们认为满足其**子树内所有有限制点的限制**的子树是**均好的子树**。显然，要想使一个子树成为均好的子树，可能有**多种染色方法**。\n\n你需要回答以下两种询问：\n\n- `Z k c`，表示给点 $k$ 以均等概率在 $[0,c]$ 中选择一个数 $f$，然后给点 $k$ 直接加上 $f$ 个没有限制的儿子，其它儿子状态不变。问点 $k$ 为根的子树成为**均好的子树**的期望染色方法数量。\n- `H k`，表示如果去掉 $k$ 的所有有限制儿子的限制，询问 $k$ 为根的子树成为**均好的子树**的染色方法数量。\n\n我们并没有必要点燃更多的烟花，因此所有的询问都是相互独立的，没有询问会真的影响原树。\n\n我们深知可能复现不了当时完整的情况，历史太过斑驳，可能的烟花组合成千上万，因此你只需要得到答案对 $998244353$ 这个大质数取模的值。"},{"iden":"input","content":"第一行两个整数 $n,p$，表示树的节点个数与限制个数。\n\n接下来 $n-1$ 行，每行两个数 $u,v$，表示 $u,v$ 之间有一条直连边。这 $n-1$ 行表示树的结构。\n\n接下来 $p$ 行，每行两个数 $(x_i,y_i)$，表示限制以 $x_i$ 点为根的子树，需要恰好存在 $y_i$ 个黑点在其子树内。\n\n接下来一行一个整数 $q$，表示询问个数。\n\n接下来 $q$ 行，每行一个字符另加 $1$ 或 $2$ 个整数表示题目中说明的询问。"},{"iden":"output","content":"为了减小输出量，我们假设第 $i$ 个询问（$i$ 从 $1$ 开始）的答案为 $ans_i$，你只需要输出一行，表示所有询问的 $i\\times ans_i$ 的异或和。最终的异或和以及每一个 $i\\times ans_i$ 都**无需**对 $998244353$ 取模，但每个询问的答案 $ans_i$ 是对其取模后的答案。\n\n**注意：std 不依赖于输出方式。也就是说，std 可以独立获取每一个询问的答案。**"},{"iden":"note","content":"### 样例解释\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/523p3yhk.png)\n\n如图为样例 #1 的烟花，构成一个有 $14$ 个点，其中 $5$ 个限制点的树。与题目中不同的是，我们用红色烟花表示限制点，蓝色烟花表示无限制点。红色烟花右上角的浅蓝色数字表示其限制的黑点数量。\n\n初始情况下每一个点为根子树的合法烟花燃放方法数量如下（从左至右第 $i$ 项表示以第 $i$ 个点为根的子树的答案）：\n\n$$\n[320,10,4,4,2,8,1,2,2,1,2,2,1,1]\n$$\n\n下面我们给出询问的答案与部分解释：\n\n- `Z 2 5`，为 $2$ 号点添加 $i$ 个儿子后的 $2$ 号点子树内合法烟花燃放数量表示为此数列的第 $i+1$ 项：$[10,20,35,56,84,120]$。总期望即为 $\\frac{325}{6}$。对 $998244353$ 取模之后得到 $166374113$。\n- `H 14`，由于 $14$ 号点没有儿子，因此答案仍然为 $1$。\n- `Z 7 3`，共有 $10$ 种可能的合法烟花燃放方案，总期望即为 $\\frac{5}{2}$，对 $998244353$ 取模之后得到 $499122179$。\n- `Z 7 1` 的答案为 $499122178$。\n- `H 6` 的答案为 $16$。\n- `Z 1 9` 的答案为 $32736$。\n- `H 1`，去除 $1$ 的所有有限制儿子（仅有节点 $2$）的限制后有 $1024$ 种可能的合法烟花燃放方案。\n- `H 8` 的答案为 $8$。\n- `H 12` 没有儿子，因此答案不变，此询问的答案仍然为 $2$。\n- `Z 10 1` 的答案为 $1$。\n\n最终，所有询问的 $i\\times ans_i$ 的异或和即为 $665340330$。\n\n### 数据范围\n\n**请注意常数因子对程序效率的影响。**\n\n**本题采用捆绑测试与子任务依赖。**\n\n下面定义 $S=3\\times 10^5$。\n\n| $\\rm Subtask$ | $n$ | $q$ | $y_i$ | $c$ | 特殊性质 | 得分 | 子任务依赖 |\n| :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: |\n| $1$ | $\\leqslant 10$ | $\\leqslant 10$ | $\\leqslant 5$ | $\\leqslant 5$ | 无 | $10$ | 无 |\n| $2$ | $\\leqslant 200$  | $\\leqslant 200$ | $\\leqslant 200$ | $\\leqslant 200$ | 无 | $15$ | $1$ |\n| $3$ | $\\leqslant S$ | $\\leqslant S$ | $\\leqslant S$ | $\\leqslant 10$ | 无 | $20$ | $1,2$ |\n| $4$ | $\\leqslant S$ | $\\leqslant S$ | $\\leqslant S$ | $\\leqslant S$ | $A$ | $15$ | 无 |\n| $5$ | $\\leqslant S$ | $\\leqslant S$ | $\\leqslant S$ | $\\leqslant S$ | $B$ | $20$ | 无 |\n| $6$ | $\\leqslant S$ | $\\leqslant S$ | $\\leqslant S$ | $\\leqslant S$ | 无 | $20$ | $1,2,3,4,5$ |\n\n特殊性质 $A$：$p=0$。\n\n特殊性质 $B$：满足不存在 `Z` 询问。\n\n对于 $100\\%$ 的数据，存在输入的所有数均为 $\\leqslant S$ 的整数。特别地，存在 $0\\leqslant p\\leqslant n$，输入的任何树的节点编号 $x$ 都满足 $1\\leqslant x \\leqslant n$。保证输入的询问字符都为 `Z` 或 `H`，输入的一定是一棵树。保证对于所有限制存在 $x_i\\neq x_j(i\\neq j)$。\n\n\n------------\n\n冬天的最后一场雪如约而至，很快又要迎来一个新的春天。万物都在等待复苏，可峰城里的一个小巷子，再也不复往日繁荣。\n\n八十多年过去，我们早已找不到当初的巷子，只留下这样一个故事。\n\n感谢你放的烟花。"}],"translated_statement":null,"sample_group":[["14 5\n1 2\n1 3\n4 1\n5 2\n2 6\n3 7\n3 8\n9 4\n12 6\n11 6\n6 10\n8 13\n14 8\n2 3\n10 0\n7 1\n13 1\n14 0\n10\nZ 2 5\nH 14\nZ 7 3\nZ 7 1\nH 6\nZ 1 9\nH 1\nH 8\nH 12\nZ 10 1","665340330"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}