Alek likes competitive programming, especially surreal trees. A surreal tree, as the name suggests, is a surreal number on a tree.

Alek believes that for a constant $k$, a string is called a "$k$-surreal number string" if it only contains the characters $\texttt{'\{'}$, $\texttt{'|'}$, and $\texttt{'\}'}$, and satisfies the following:

• The empty string is a $k$-surreal number string;
• If $s$ and $t$ are $k$-surreal number strings, then $s + t$ (where $+$ denotes string concatenation) is a $k$-surreal number string;
• If $k + 1$ strings $s_1, s_2, \dots, s_{k + 1}$ are all $k$-surreal number strings, then $\texttt{'\{'} + s_1 + \texttt{'|'} + s_2 + \texttt{'|'} + \dots + \texttt{'|'} + s_{k + 1} + \texttt{'\}'}$ is a $k$-surreal number string;
• $k$-surreal number strings are limited to these definitions.

Given an unrooted tree with $n$ nodes, labeled $1 \sim n$. Each node $i$ has a character $a_i \in \{\texttt{'\{'}, \texttt{'|'}, \texttt{'\}'}\}$.

Given an integer $m$, Alek wants you to find, for each $k = 0, 1, \dots, m$: how many ordered pairs $(x, y)$ with $1 \leq x, y \leq n$ exist such that the string formed by concatenating the characters on the unique simple path from node $x$ to node $y$ in the tree is a $k$-surreal number string.

Input

The first line contains two integers $n$ and $m$, representing the number of nodes in the tree and the upper bound of $k$ for which to calculate the answer.

The second line contains a string $a$, where the $i$-th character of $a$ represents the character at node $i$.

The next $n - 1$ lines each contain two integers $x$ and $y$, representing an edge between node $x$ and node $y$.

Output

Output a single line containing $m + 1$ integers, representing the answers for $k = 0, 1, \dots, m$ respectively.

Examples

Input 1

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

Output 1

1 2 0 0

Input 2

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

Output 2

2 0 1 1 0 0 0 0 0

Input 3

See the additional file ex_surreal3.in/ans.

Constraints

For all data, $2 \leq n \leq 10^5$, $0 \leq m \leq n - 2$, and $a_i \in \{\texttt{'\{'}, \texttt{'|'}, \texttt{'\}'}\}$.

• Subtask 1 (5 points): $n \leq 4601$;
• Subtask 2 (20 points): For every edge $(x, y)$, $y = x + 1$;
• Subtask 3 (5 points): $a_i \neq \texttt{'|'}$, $m = 0$;
• Subtask 4 (15 points, depends on Subtask 3): $m \leq 3$;
• Subtask 5 (25 points, depends on Subtask 1): $n \leq 5 \times 10^4$;
• Subtask 6 (30 points, depends on Subtask 1, 2, 3, 4, 5): No special constraints.