Alek 喜欢打信息竞赛, 尤其喜欢超现实树. 超现实树, 顾名思义, 就是树上的超现实数.

Alek 认为, 对于常数 $k$, 一个字符串被称为 "$k$-超现实数串", 如果其只包含字符 $\texttt{`\{'}, \texttt{`|'}, \texttt{`\}'}$, 且:

• 空串为 $k$-超现实数串;
• 如果 $s, t$ 为 $k$-超现实数串, 那么 $s + t$ (加法表示字符串拼接) 为 $k$-超现实数串;
• 如果 $k + 1$ 个字符串 $s_1, s_2, \cdots, s_{k + 1}$ 都是 $k$-超现实数串, 那么 $\texttt{`\{'} + s_1 + \texttt{`|'} + s_2 + \texttt{`|'} + \cdots + \texttt{`|'} + s_{k + 1} + \texttt{`\}'}$ 为 $k$-超现实数串;
• $k$-超现实数串仅限于此.

给定一棵 $n$ 个点的无根树, 节点编号为 $1 \sim n$. 每个点 $i$ 上有一个字符 $a_i \in \{\texttt{`\{'}, \texttt{`|'}, \texttt{`\}'}\}$.

给定整数 $m$, Alek 希望你对 $k = 0, 1, \cdots, m$ 分别求出: 有多少有序对 $(x, y)$, $1 \leq x, y \leq n$, 使得树上从点 $x$ 到点 $y$ 的唯一简单路径上的字符依次拼接所得字符串是 $k$-超现实数串.

输入格式

第一行两个整数 $n, m$, 分别表示树的节点数, 和需要求答案的 $k$ 的上限.

第二行一个字符串 $a$, $a$ 的第 $i$ 个字符表示点 $i$ 上的字符.

接下来 $n - 1$ 行, 每行两个整数 $x, y$, 表示存在一条连接点 $x$ 和点 $y$ 的边.

输出格式

输出一行 $m + 1$ 个整数, 分别表示 $k = 0, 1, \cdots, m$ 时的答案.

样例

样例 1 输入

5 3
|{}}}
2 1
3 2
4 1
5 1

样例 1 输出

1 2 0 0

样例 2 输入

10 8
|}||}{|{{{
2 1
3 1
4 3
5 2
6 5
7 5
8 4
9 2
10 3

样例 2 输出

2 0 1 1 0 0 0 0 0

样例 3

见附加文件 ex_surreal3.in/ans.

限制与约定

对于所有数据, 有 $2 \leq n \leq 10^5$, $0 \leq m \leq n - 2$, $a_i \in \{\texttt{`\{'}, \texttt{`|'}, \texttt{`\}'}\}$.

• Subtask 1 (5 分): $n \leq 4601$;
• Subtask 2 (20 分): 对每条边 $(x, y)$ 有 $y = x + 1$;
• Subtask 3 (5 分): $a_i \neq \texttt{`|'}$, $m = 0$;
• Subtask 4 (15 分, 依赖 Subtask 3): $m \leq 3$;
• Subtask 5 (25 分, 依赖 Subtask 1): $n \leq 5 \times 10^4$;
• Subtask 6 (30 分, 依赖 Subtask 1, 2, 3, 4, 5): 无特殊限制.

时间限制: 1s; 空间限制: 512MB.