#include <cstdio> #include <cmath> #include <cstring> #include <vector> #include <algorithm> #define db float #define pb emplace_back using std::vector; const int N=2000005, B=5; namespace Poly{ template<class _T> struct complex{ _T x, y; complex() {} complex(_T a, _T b) { x=a, y=b; } complex operator *(const complex &a) const { return complex(a.x*x-a.y*y, a.x*y+a.y*x); } void operator *=(const complex &a) { *this=complex(a.x*x-a.y*y, a.x*y+a.y*x); } complex operator +(const complex &a) const { return complex(a.x+x, a.y+y); } complex operator -(const complex &a) const { return complex(x-a.x, y-a.y); } void operator /=(const int &a) { x/=a, y/=a; } complex operator /(const int &a) const { return complex(x/a, y/a); } complex conj (void) const { return complex(x, -y); } inline _T real(void) { return x; } }; const db Pi=acos(-1.0); int rev[N]; complex<db> wn[N]; inline int glim(int n) { int ret=0; while(n) n>>=1, ++ret; return ret; } void init(int l) { for(int i=0; i<(1<<l); ++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1)); for(int i=1; i<(1<<l); i<<=1) { for(int j=0; j<i; ++j) wn[i+j]=complex<db>(cos(Pi*j/i), sin(Pi*j/i)); } } void FFT(complex<db> *f, int l, int mod) { int n=1<<l; for(int i=0; i<n; ++i) if(i<rev[i]) std::swap(f[i], f[rev[i]]); for(int len=2; len<=n; len<<=1) { int mid=len>>1; for(int i=0; i<n; i+=len) for(int j=i; j<i+mid; ++j) { complex<db> x=f[j], y=f[j+mid]*wn[j+mid-i]; f[j]=x+y, f[j+mid]=x-y; } } if(mod) { std::reverse(f+1, f+n); for(int i=0; i<n; ++i) f[i]/=n; } } } using namespace Poly; int n, m, a[N], c[N], cc[N], cnt[N], blc=2; vector<int> id[B]; complex<db> f[N], h[N]; namespace iobuff{ const int LEN=1000000; char in[LEN+5], out[LEN+5]; char *pin=in, *pout=out, *ed=in, *eout=out+LEN; inline char gc(void) { return pin==ed&&(ed=(pin=in)+fread(in, 1, LEN, stdin), ed==in)?EOF:*pin++; } inline void pc(char c) { pout==eout&&(fwrite(out, 1, LEN, stdout), pout=out); (*pout++)=c; } inline void flush() { fwrite(out, 1, pout-out, stdout), pout=out; } template<typename T> inline void scan(T &x) { static int f; static char c; c=gc(), f=1, x=0; while(c<'0'||c>'9') f=(c=='-'?-1:1), c=gc(); while(c>='0'&&c<='9') x=10*x+c-'0', c=gc(); x*=f; } template<typename T> inline void putint(T x, char div) { static char s[15]; static int top; top=0; x<0?pc('-'), x=-x:0; while(x) s[top++]=x%10, x/=10; !top?pc('0'), 0:0; while(top--) pc(s[top]+'0'); pc(div); } } using namespace iobuff; int main() { //freopen("a.in","r",stdin); //freopen("a.out","w",stdout); scan(n), scan(m); for(int i=1; i<=n; ++i) scan(a[i]), ++cnt[a[i]]; for(int i=1; i<=m; ++i) if(cnt[i]) id[std::min(blc+1, cnt[i])].pb(i); for(int i=1; i<=m; ++i) if(cnt[i]) cc[i]=1; int lm=glim(2*m), rm=1<<lm; init(lm); for(int i=1, ok=0; i<=blc; ++i) { if(i==1||id[i-1].size()) { for(int i=0; i<rm; ++i) f[i]=complex<db>(cc[i], 0); FFT(f, lm, 0); } for(int i=0; i<rm; ++i) h[i]=h[i]+f[i]*f[i]; for(int x:id[i]) --cc[x]; } for(auto x=id[blc+1].begin(); x!=id[blc+1].end(); ++x) { c[2**x]+=cnt[*x]-blc; for(auto y=id[blc+1].begin(); y!=x; ++y) c[*x+*y]+=2*(std::min(cnt[*x], cnt[*y])-blc); } FFT(h, lm, 1); for(int i=1; i<=m; ++i) c[i]+=(int)(h[i].x+0.5); for(int i=2; i<=m; i+=2) c[i]-=cnt[i>>1]-((cnt[i>>1]>>1)<<1); for(int i=1; i<=m; ++i) putint(c[i]>>1, ' '); flush(); return 0; }