时空限制

2.5s/1024M

题目描述

你在公园里捡到了一棵树，编号为 $1\dots n$，每条边上有两种操作：

• * k 乘上 $k$。
• sqr k 平方 $k$ 次。

定义 $d(u,v)$ 为在从 $u$ 到 $v$ 的路径上，初始值为 $1$，依次执行边上的操作，最后的结果。

你需要对于每个 $i$ 求出 $\sum_{j=1}^{n}d(i,j)$ 对 $998244353$ 取模的值。

你现在要解决这个问题。

格式

输入格式

第一行一个正整数 $n$。

接下来 $n-1$ 行，每行描述一条边及其操作。格式如下： u v op k 其中 $u, v$ 为一条边连接的两个节点编号；op 为一个字符串，取值为 * 或 sqr，表示操作类型；$k$ 为操作对应的参数（含义见题目描述）。

输出格式

一行 $n$ 个整数，第 $i$ 个整数为 $\sum_{j=1}^{n}d(i,j)$ 对 $998244353$ 取模的值。

样例

样例输入 #1

5
1 2 sqr 1
2 3 sqr 2
3 4 sqr 5
4 5 * 1

样例输出 #1

5 5 5 5 5

样例输入 #2

9
6 9 * 994813574
3 1 sqr 508749089
5 7 * 307270927
6 8 sqr 918624732
2 4 * 469548409
3 7 sqr 929348146
2 1 sqr 658359034
6 2 sqr 170255482

样例输出 #2

773388563 773388563 773388563 873306548 199507042 773388563 773388563 773388563 584505986

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

特殊性质 A：保证无平方操作。

特殊性质 B：保证树为链。

对于 $100\%$ 的数据，$0 \le k<998244353$，$2\le n \le 5\times 10^5$，保证图为树。