Problem: Our child likes computer science very much, especially he likes binary trees.

Consider the sequence of n distinct positive integers: c1, c2, ..., cn. The child calls a vertex-weighted rooted binary tree good if and only if for every vertex v, the weight of v is in the set {c1, c2, ..., cn}. Also our child thinks that the weight of a vertex-weighted tree is the sum of all vertices' weights.

Given an integer m, can you for all s (1 ≤ s ≤ m) calculate the number of good vertex-weighted rooted binary trees with weight s? Please, check the samples for better understanding what trees are considered different.

We only want to know the answer modulo 998244353 (7 × 17 × 223 + 1, a prime number).

Input

The first line contains two integers n, m (1 ≤ n ≤ 105; 1 ≤ m ≤ 105). The second line contains n space-separated pairwise distinct integers c1, c2, ..., cn. (1 ≤ ci ≤ 105).

Output

Print m lines, each line containing a single integer. The i-th line must contain the number of good vertex-weighted rooted binary trees whose weight exactly equal to i. Print the answers modulo 998244353 (7 × 17 × 223 + 1, a prime number).

Examples

Input

2 3
1 2


Output

1
3
9


Input

3 10
9 4 3


Output

0
0
1
1
0
2
4
2
6
15


Input

5 10
13 10 6 4 15


Output

0
0
0
1
0
1
0
2
0
5

Note

In the first example, there are 9 good vertex-weighted rooted binary trees whose weight exactly equal to 3:

<image>

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 410001;
const int p = 998244353;
int a[maxn], ans[maxn], tmp[maxn];
int rev(int a);
void ntt(int *a, int k, int *ans, bool rev);
void juanji(int *a, int *b, int *c, int k);
void inv(int *a, int k, int *ans);
void sqrt(int *a, int k, int *ans);
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  a[0] = 1;
  for (int i = 1; i <= n; i++) {
    int x;
    scanf("%d", &x);
    if (x <= m) a[x] = p - 4;
  }
  int cnt = 0;
  while ((1 << cnt) < m + 1) cnt++;
  sqrt(a, cnt, tmp);
  tmp[0]++;
  inv(tmp, cnt, ans);
  for (int i = 1; i <= m; i++) {
    printf("%d\n", ans[i] * 2 % p);
  }
  return 0;
}
int fast_pow(int a, int t) {
  int ans = 1;
  for (int i = 31; i >= 0; i--) {
    ans = (long long)ans * ans % p;
    if (t >> i & 1) ans = (long long)ans * a % p;
  }
  return ans;
}
int rev3 = rev(3);
void ntt(int *a, int k, int *ans, bool rev) {
  static int bit_rev[maxn];
  int n = 1 << k;
  for (int i = 0; i < n; i++) {
    bit_rev[i] = (bit_rev[i >> 1] >> 1) | ((i & 1) << (k - 1));
  }
  for (int i = 0; i < n; i++) {
    ans[bit_rev[i]] = a[i];
  }
  for (int t = 1; t <= k; t++) {
    int w_n = fast_pow(rev ? rev3 : 3, (p - 1) / (1 << t));
    for (int j = 0; j < n; j += (1 << t)) {
      int w = 1;
      for (int i = j; i < j + (1 << t - 1); i++) {
        int ans0 = ans[i];
        int ans1 = ans[i + (1 << t - 1)];
        ans[i] = (ans0 + (long long)w * ans1) % p;
        ans[i + (1 << t - 1)] = (ans0 + (long long)(p - w) * ans1) % p;
        w = (long long)w_n * w % p;
      }
    }
  }
  if (rev) {
    int rn = ::rev(n);
    for (int i = 0; i < n; i++) {
      ans[i] = (long long)rn * ans[i] % p;
    }
  }
}
void juanji(int *a, int *b, int *c, int k) {
  static int fa[maxn], fb[maxn];
  int n = 1 << k;
  ntt(a, k, fa, 0);
  ntt(b, k, fb, 0);
  for (int i = 0; i < n; i++) {
    fa[i] = (long long)fa[i] * fb[i] % p;
  }
  ntt(fa, k, c, 1);
}
void inv(int *a, int k, int *ans) {
  static int ta[maxn], fa[maxn], tmp[maxn];
  memset(ta, 0, sizeof(ta));
  memset(tmp, 0, sizeof(tmp));
  memset(fa, 0, sizeof(fa));
  ans[0] = rev(a[0]);
  for (int i = 1; i <= k; i++) {
    int len = 1 << i;
    for (int j = 0; j < len; j++) {
      ta[j] = a[j];
    }
    ntt(ta, i + 1, fa, 0);
    ntt(ans, i + 1, tmp, 0);
    for (int j = 0; j < 2 * len; j++) {
      tmp[j] = (long long)tmp[j] * tmp[j] % p * fa[j] % p;
    }
    ntt(tmp, i + 1, ta, 1);
    for (int j = 0; j < len; j++) {
      ans[j] = ((long long)2 * ans[j] - ta[j] + p) % p;
    }
  }
}
void sqrt(int *a, int k, int *ans) {
  static int ta[maxn], tmp[maxn];
  memset(ta, 0, sizeof(ta));
  ans[0] = 1;
  int rev2 = rev(2);
  for (int i = 1; i <= k; i++) {
    int len = 1 << i;
    for (int j = 0; j < len; j++) {
      ta[j] = a[j];
    }
    for (int j = 0; j < 2 * len; j++) {
      tmp[j] = 0;
    }
    inv(ans, i, tmp);
    juanji(ta, tmp, tmp, i + 1);
    for (int j = 0; j < len; j++) {
      ans[j] = (long long)rev2 * (ans[j] + tmp[j]) % p;
    }
  }
}
int d, x, y;
void gcd(int a, int b) {
  if (!b) {
    d = a;
    x = 1;
    y = 0;
    return;
  }
  gcd(b, a % b);
  int t = x;
  x = y;
  y = t - a / b * y;
}
int rev(int a) {
  gcd(a, p);
  if (x < 0) x += p;
  return x;
}