전통에서 과감히 벗어나 올해 그랜드 대회에서는 두 엘리트 팀인 레드 팀(Team Red)과 블루 팀(Team Blue)이 정면 승부를 벌이는 특별 매치인 올스타 쇼다운(All-Star Showdown)이 열립니다. 일반적인 대회 방식과 달리, 이 경기에서는 모든 참가자가 정확히 하나의 팀에 배정되기만 한다면 팀 인원수를 유연하게 구성할 수 있습니다.

명예의 전당에서 선발된 $n$명의 올스타 참가자가 있습니다. 각 참가자 $i$는 알고리즘 통찰력, 구현 속도, 디버깅 회복력이라는 세 가지 핵심 차원에서 평가됩니다. 이러한 속성은 양의 정수 $(x_i, y_i, z_i)$로 정량화되어 그들의 경쟁 프로필을 나타내는 3차원 능력 벡터를 형성합니다. 또한, 각 참가자 $i$에게는 팀 성과를 증폭시키는 능력을 반영하는 양의 정수 시너지 값 $w_i$가 부여됩니다. 한 팀의 전체 팀 가치는 소속 팀원들의 시너지 값의 곱으로 정의됩니다.

경쟁의 무결성을 유지하고 비슷한 스타일의 코더 집단이 지배하는 것을 방지하기 위해 주최측은 엄격한 다양성 규칙을 적용합니다. 단일 팀 내에서 임의의 두 팀원의 능력 벡터 사이의 유클리드 거리는 최소 $d$ 이상이어야 합니다. 공식적으로, 같은 팀에 속한 서로 다른 임의의 두 참가자 $i$와 $j$에 대해 $\sqrt{(x_i - x_j)^2 + (y_i - y_j)^2 + (z_i - z_j)^2} \ge d$를 만족해야 합니다. 이를 통해 각 팀이 다양한 문제 해결 접근 방식을 고루 갖추도록 보장합니다.

조직위원회는 모든 유효한 배정의 조합적 구조를 분석하고자 합니다. 구체적으로, 각 정수 $k = 1, 2, \dots, n - 1$에 대해, 레드 팀이 정확히 $k$명의 참가자를 포함하는 모든 유효한 분할에서 레드 팀 가치의 합을 구하려고 합니다.

답이 매우 클 수 있으므로 $998\,244\,353$으로 나눈 나머지를 출력하세요.

입력

각 테스트 파일에는 하나의 테스트 케이스만 주어집니다.

첫 번째 줄에 두 정수 $n$과 $d$ ($2 \le n \le 10^5$, $1 \le d \le 10^8$)가 주어집니다.

다음 $n$개의 줄 중 $i$번째 줄에는 네 정수 $x_i$, $y_i$, $z_i$, $w_i$ ($1 \le x_i, y_i, z_i, w_i \le 10^8$)가 주어지며, 이는 참가자 $i$의 능력 벡터와 시너지 값을 나타냅니다.

출력

$(n - 1)$개의 줄을 출력합니다. 그중 $i$번째 줄에는 레드 팀이 정확히 $i$명의 참가자를 포함하는 모든 유효한 분할에 대한 레드 팀 가치의 합을 $998\,244\,353$으로 나눈 나머지를 나타내는 정수를 출력합니다.

예제

예제 입력 1

3 1
1 1 1 1
1 2 1 10
1 2 3 100

예제 출력 1

111
1110

예제 입력 2

3 2
1 1 1 1
1 2 1 10
1 2 3 100

예제 출력 2

11
1100

예제 입력 3

3 2
2 1 1 1
1 2 1 10
1 1 2 100

예제 출력 3

0
0