小 R 最近沉迷于一款游戏。在游戏中，小 R 的任务是捕捉一些史莱姆。游戏的地图上有 $n$ 座城堡，编号为 $1$ 到 $n$。有 $n-1$ 条无向边，每条边连接两座城堡，任意两座城堡之间都连通。即这 $n$ 座城堡构成一棵树。在每一座城堡中都有一些红色史莱姆和绿色史莱姆，编号为 $i$ 的城堡有 $r_i$ 只互不相同的红色史莱姆和 $g_i$ 只互不相同的绿色史莱姆。小 R 从 $1$ 号城堡出发，当他经过一座城堡（包括 $1$ 号城堡）时，他会捕捉这座城堡中的任意一只史莱姆（即任意一只红色史莱姆或任意一只绿色史莱姆，不能一只都不捕捉，也不能捕捉超过一只），然后沿着一条边走向一座之前没有经过的城堡，如果不存在没有经过的城堡，则游戏结束。即如果把 $1$ 号城堡作为根，小 R 经过的路径一定是一条从根到某一个叶子节点的链，并且他会在每一个经过的城堡捕捉正好一只史莱姆。

小 R 希望捕捉正好 $k$ 只绿色史莱姆（不能多也不能少），他想知道有多少种不同的方案。方案 A 和方案 B 相同当且仅当方案 A 中捕捉的史莱姆与方案 B 中捕捉的史莱姆完全相同。需要注意的是地图上任意两只史莱姆都是互不相同的。由于他还没有想好 $k$ 的具体值，所以你需要同时输出 $k=0,1,2,\dots,n$ 的答案。由于答案可能很大，你只需要输出答案模 $998,244,353$ 的值。

输入格式

从标准输入读入数据。

第一行一个正整数 $n$ 和一个字符串 $type$，分别表示城堡的数量和数据的类型。$type$ 字符串是为了能让大家更方便地获得部分分，你可能不需要用到这个输入。其具体含义在【子任务】中有解释。

第二行 $n$ 个正整数，第 $i$ 个正整数表示 $r_i$，即 $i$ 号城堡中红色史莱姆的数量。保证 $1\le r_i \le10^8$。

第三行 $n$ 个正整数，第 $i$ 个正整数表示 $g_i$，即 $i$ 号城堡中绿色史莱姆的数量。保证 $1\le g_i\le10^8$。

接下来 $n-1$ 行每行两个正整数 $u,v$，表示 $u,v$ 之间有一条边。数据保证输入的边构成一棵树。

输出格式

输出到标准输出。

输出 $n+1$ 行，分别表示 $k=0,1,2,\dots,n$ 的答案。

样例

输入

4 A1
3 2 2 1
2 4 1 3
1 2
1 3
3 4

输出

12
41
31
6
0

解释

小 R 有 $2$ 种路线，分别是 $1-2$ 和 $1-3-4$。因为在每个经过的城堡都至少要捕捉一只史莱姆，所以两种路线对应的方案一定是两两不同的。假设选择路线 $1-2$，若$k=0$，则需在 $1$ 号城堡和 $2$ 号城堡都需捕捉红色史莱姆，因为这两座城堡分别有3只和2只不同的红色史莱姆，所以方案数为 $3\times 2=6$。若 $k=1$，则可以在 $1$ 捉红的在 $2$ 捉绿，或在 $1$ 捉绿的在 $2$ 捉红的，方案数为$3\times 4+2\times 2=16$。$k=2$ 的方案数为 $2\times 4=8$。同理如果选择路线 $1-3-4$，$k=0,1,2,3$ 的方案数为 $6,25,23,6$。所以最终的答案为 $12,41,31,6,0$。

样例

输入

6 D1
7 3 2 5 9 1
2 6 4 4 4 3
1 6
2 5
3 5
3 4
5 6

输出

819
5197
10896
9036
3152
384
0

样例三

见下载目录下的 ex_3.in 与 ex_3.ans。

样例四

见下载目录下的 ex_4.in 与 ex_4.ans。

子任务

本题共有 20 个测试点，每个测试点 5 分。各测试点约定如下：

​

数据类型的含义：

A：$r_i\le 5,g_i \le 5$

B：$r_i=g_i$

C：$g_i=1$

D：无限制

0：一条链（$i$ 号城堡与 $i+1$ 号城堡相连）

1：无限制

在提交代码后将为你评测预测试数据并返回结果。本题的预测试数据包含 $8$ 个测试点，每个测试点的数据规模限制与表格中的各行相同。

注意：预测试数据的评测结果与最终评测结果没有关系。