세인트 워털루에는 $n$개의 도시가 있으며, 이 도시들은 $n-1$개의 무방향 항공 노선으로 연결되어 있어 임의의 두 도시 사이를 항공 노선을 이용해 이동할 수 있습니다.

두 도시 사이의 거리가 최대 $x$번의 비행으로 이동 가능하다면, 이 두 도시는 좋은 관계에 있다고 합니다.

또한, 어떤 $k$개의 도시 집합에 속한 모든 도시 쌍이 서로 좋은 관계에 있다면, 이 집합을 친밀한 집합이라고 합니다.

$1 \le k \le n$인 각 $k$에 대하여 친밀한 도시 집합의 개수를 구해야 합니다. 이 값들은 매우 클 수 있으므로, $998\,244\,353$으로 나눈 나머지를 구하십시오.

입력

첫 번째 줄에는 두 정수 $n, x$ ($1 \le n \le 300\,000$, $0 \le x \le n - 1$)가 주어집니다. 이는 세인트 워털루의 도시 수와 $x$를 의미합니다.

다음 $n-1$개의 줄에는 간선에 대한 정보가 주어지며, $i$번째 줄에는 $i$번째 항공 노선으로 연결된 두 도시의 인덱스 $a, b$ ($1 \le a, b \le n$)가 주어집니다.

출력

$1, 2, \dots, n$개의 도시로 이루어진 친밀한 집합의 개수를 각각 $998\,244\,353$으로 나눈 나머지를 출력하십시오.

예제

입력 1

1 0

출력 1

1

입력 2

5 1
1 2
2 3
3 4
4 5

출력 2

5 4 0 0 0

입력 3

4 2
1 2
1 3
1 4

출력 3

4 6 4 1

참고

두 번째 예제에서 가능한 모든 친밀한 집합은 크기가 1 또는 2이며, 각 크기에 대한 친밀한 집합의 개수는 각각 도시의 수와 항공 노선의 수와 같습니다.

세 번째 예제에서는 임의의 도시에서 다른 모든 도시로 최대 $x$번의 비행으로 이동할 수 있으므로, $k$개의 도시로 이루어진 친밀한 집합의 개수는 $\binom{4}{k}$입니다.