I used to be a jelly-hyper like you, then I took an arrow in the knee.

I think I'd better use jelly-jumps to prevent losing speed too quickly.

If I really intended to leave here to do something else instead of writing miscellaneous things here, the things just mentioned might be very useful.

Given a tree with $n$ weighted nodes and a feasible distance value $k$, a set $S$ is called "legal" if and only if the distance between any two distinct elements in $S$ on the tree is at least $k$.

For each $m = 1, 2, 3, \dots, n$, find the number of ways to partition the set of vertices of this tree into $m$ unordered non-empty sets, such that each vertex is contained in exactly one of the $m$ sets, and each set is "legal". Output the answers modulo $998244353$.

Input

The first line contains two positive integers $n$ and $k$, representing the number of vertices in the tree and the feasible distance value.

The next $n-1$ lines each contain three integers $x, y, z$, representing the two endpoints of an edge in the tree and the weight of that edge.

Output

A single line containing $n$ integers, representing the answers for $m = 1, 2, 3, \dots, n$ respectively.

Examples

Input 1

5 2
1 2 1
1 3 1
2 4 1
2 5 1

Output 1

0 1 7 6 1

Input 2

10 3
1 2 1
1 3 1
2 4 1
2 5 1
3 6 1
3 7 1
4 8 1
4 9 1
5 10 1

Output 2

0 0 0 16 308 836 674 206 25 1

Constraints

$2 \leq n \leq 100000, 1 \leq k \leq 10^{14}, 1 \leq x, y \leq n, 1 \leq z \leq 10^9$.

• Subtask 1 (10 pts): $n \leq 10$
• Subtask 2 (15 pts): $n \leq 2000$, and all edge weights are 1.
• Subtask 3 (15 pts): $n \leq 2000$
• Subtask 4 (15 pts): For $1 \leq i \leq n-1$, the $i$-th edge satisfies $x=i, y=i+1$, and all edge weights are 1.
• Subtask 5 (15 pts): For $1 \leq i \leq n-1$, the $i$-th edge satisfies $x=i, y=i+1$.
• Subtask 6 (15 pts): All edge weights are 1.
• Subtask 7 (15 pts): No special restrictions.

The order of subtasks is not related to their difficulty.