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 N = 4e5 + 5, G = 3, P = 998244353;
int w[N], w_1[N];
int a[N], b[N], c[N];
int n, tn, inv2;
int pow_mod(int x, int k) {
  int r = 1;
  while (k) {
    if (k & 1) (r = (long long)r * x % P);
    x = (long long)x * x % P;
    k >>= 1;
  }
  return r;
}
void PreCalc() {
  tn = ++n;
  for (n = 1; n < tn; n <<= 1)
    ;
  n <<= 1;
  w[0] = w_1[0] = 1;
  int wn = pow_mod(3, (P - 1) / n);
  for (int i = 1; i < n; i++) w[i] = w_1[n - i] = (long long)w[i - 1] * wn % P;
  inv2 = P / 2 + 1;
}
void print(int *a, int n) {
  for (int i = 0; i < n; i++) printf("%d ", a[i]);
  puts("");
}
void NTT(int *x, int *w, int d, int n) {
  for (int i = 0, t = 0; i < n; i++) {
    if (i < t) swap(x[i], x[t]);
    for (int j = (n >> 1); (t ^= j) < j; j >>= 1)
      ;
  }
  int t;
  for (int i = n; i > 2; i >>= 1, d++)
    ;
  for (int s = 1; s < n; s <<= 1, d--)
    for (int i = 0; i < n; i += (s << 1))
      for (int j = 0; j < s; j++) {
        t = (long long)x[i + j + s] * w[j << d] % P;
        x[i + j + s] = (x[i + j] - t + P) % P;
        x[i + j] = (x[i + j] + t) % P;
      }
}
void GetPolyInv(int *a, int *b, int k, int n) {
  static int t[N];
  if (n == 1) {
    b[0] = pow_mod(a[0], P - 2);
    return;
  }
  GetPolyInv(a, b, k + 1, n >> 1);
  int nn = n + n;
  for (int i = 0; i < n; i++) t[i] = a[i];
  for (int i = n; i < nn; i++) t[i] = 0;
  NTT(t, w, k, nn), NTT(b, w, k, nn);
  for (int i = 0; i < nn; i++) t[i] = (2 - (long long)t[i] * b[i] % P + P) % P;
  for (int i = 0; i < nn; i++) b[i] = (long long)b[i] * t[i] % P;
  NTT(b, w_1, k, nn);
  int inv = pow_mod(nn, P - 2);
  for (int i = 0; i < n; i++) b[i] = (long long)b[i] * inv % P;
  for (int i = n; i < nn; i++) b[i] = 0;
}
void GetSquRoot(int *a, int *b, int k, int n) {
  static int t[N], t2[N];
  if (n == 1) {
    b[0] = 1;
    return;
  }
  GetSquRoot(a, b, k + 1, n >> 1);
  int nn = n << 1;
  for (int i = 0; i < n; i++) t[i] = a[i];
  for (int i = n; i < nn; i++) t[i] = 0;
  memset(t2, 0, sizeof(int) * nn);
  GetPolyInv(b, t2, k, n);
  NTT(b, w, k, nn), NTT(t, w, k, nn), NTT(t2, w, k, nn);
  for (int i = 0; i < nn; i++)
    b[i] = (long long)inv2 * (b[i] + (long long)t[i] * t2[i] % P) % P;
  NTT(b, w_1, k, nn);
  int inv = pow_mod(nn, P - 2);
  for (int i = 0; i < n; i++) b[i] = (long long)b[i] * inv % P;
  for (int i = n; i < nn; i++) b[i] = 0;
}
int main() {
  int m, t, tn;
  scanf("%d%d", &m, &n);
  tn = n;
  for (int i = 1; i <= m; i++) scanf("%d", &t), t <= n ? a[t] = P - 4 : 0;
  a[0] = 1;
  PreCalc();
  GetSquRoot(a, b, 0, n >> 1);
  b[0] = (b[0] + 1) % P;
  GetPolyInv(b, c, 0, n >> 1);
  for (int i = 1; i <= tn; i++) printf("%d\n", 2 * c[i] % P);
  cin >> n;
  return 0;
}