#P18077. All-Star Showdown

All-Star Showdown

All-Star Showdown

有 nn 个点。第 ii 个点的三维坐标为 (xi,yi,zi)(x_i,y_i,z_i),权值为 wiw_i。

将每个点恰好分到红队或蓝队。一个划分合法,当且仅当任意两个属于同一队的不同点,其欧氏距离都不小于 dd。

红队的价值是红队所有点的权值之积。对每个 k=1,2,…,n−1k=1,2,\ldots,n-1,求所有红队恰有 kk 个点的合法划分中,红队价值的总和,对 998244353998244353 取模。

输入格式

本题只有一组数据。

第一行两个整数 n,dn,d。

接下来 nn 行,每行四个整数 xi,yi,zi,wix_i,y_i,z_i,w_i。

输出格式

输出 n−1n-1 行,第 kk 行为红队大小恰为 kk 时的答案。

数据范围

  • 2≤n≤1052\le n\le 10^5;
  • 1≤d≤1081\le d\le 10^8;
  • 1≤xi,yi,zi,wi≤1081\le x_i,y_i,z_i,w_i\le10^8。

不同点的坐标可以相同;距离恰好等于 dd 时允许同队。

样例 1

输入:

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

输出:

111
1110

样例 2

输入:

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

输出:

11
1100

样例 3

输入:

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

输出:

0
0