#include <bits/stdc++.h>
using namespace std;
template <int MOD_>
struct modnum {
  static constexpr int MOD = MOD_;
  static_assert(MOD_ > 0, "MOD must be positive");

 private:
  using ll = long long;
  int v;
  static int minv(int a, int m) {
    a %= m;
    assert(a);
    return a == 1 ? 1 : int(m - ll(minv(m, a)) * ll(m) / a);
  }

 public:
  modnum() : v(0) {}
  modnum(ll v_) : v(int(v_ % MOD)) {
    if (v < 0) v += MOD;
  }
  explicit operator int() const { return v; }
  friend std::ostream& operator<<(std::ostream& out, const modnum& n) {
    return out << int(n);
  }
  friend std::istream& operator>>(std::istream& in, modnum& n) {
    ll v_;
    in >> v_;
    n = modnum(v_);
    return in;
  }
  friend bool operator==(const modnum& a, const modnum& b) {
    return a.v == b.v;
  }
  friend bool operator!=(const modnum& a, const modnum& b) {
    return a.v != b.v;
  }
  modnum inv() const {
    modnum res;
    res.v = minv(v, MOD);
    return res;
  }
  friend modnum inv(const modnum& m) { return m.inv(); }
  modnum neg() const {
    modnum res;
    res.v = v ? MOD - v : 0;
    return res;
  }
  friend modnum neg(const modnum& m) { return m.neg(); }
  modnum operator-() const { return neg(); }
  modnum operator+() const { return modnum(*this); }
  modnum& operator++() {
    v++;
    if (v == MOD) v = 0;
    return *this;
  }
  modnum& operator--() {
    if (v == 0) v = MOD;
    v--;
    return *this;
  }
  modnum& operator+=(const modnum& o) {
    v += o.v;
    if (v >= MOD) v -= MOD;
    return *this;
  }
  modnum& operator-=(const modnum& o) {
    v -= o.v;
    if (v < 0) v += MOD;
    return *this;
  }
  modnum& operator*=(const modnum& o) {
    v = int(ll(v) * ll(o.v) % MOD);
    return *this;
  }
  modnum& operator/=(const modnum& o) { return *this *= o.inv(); }
  friend modnum operator++(modnum& a, int) {
    modnum r = a;
    ++a;
    return r;
  }
  friend modnum operator--(modnum& a, int) {
    modnum r = a;
    --a;
    return r;
  }
  friend modnum operator+(const modnum& a, const modnum& b) {
    return modnum(a) += b;
  }
  friend modnum operator-(const modnum& a, const modnum& b) {
    return modnum(a) -= b;
  }
  friend modnum operator*(const modnum& a, const modnum& b) {
    return modnum(a) *= b;
  }
  friend modnum operator/(const modnum& a, const modnum& b) {
    return modnum(a) /= b;
  }
};
template <typename T>
T pow(T a, long long b) {
  assert(b >= 0);
  T r = 1;
  while (b) {
    if (b & 1) r *= a;
    b >>= 1;
    a *= a;
  }
  return r;
}
using num = modnum<998244353>;
vector<num> fact, ifact;
void init() {
  int N = 110000;
  fact = {1};
  for (int i = 1; i < N; i++) fact.push_back(i * fact[i - 1]);
  ifact.resize(N);
  ifact.back() = 1 / fact.back();
  for (int i = N - 1; i > 0; i--) ifact[i - 1] = i * ifact[i];
}
num ncr(int n, int k) {
  if (k < 0 || k > n) return 0;
  return fact[n] * ifact[k] * ifact[n - k];
}
int main() {
  ios_base::sync_with_stdio(false), cin.tie(nullptr);
  init();
  int base = 0;
  int n, k, c;
  map<int, map<vector<int>, int> > q;
  if (0) {
    c = k = 16;
    n = (1 << c) - k;
    for (int a = k; a < (1 << c); a++) {
      int top = __builtin_ctz(a >> 4);
      base ^= a;
      vector<int> z;
      for (int j = 0; j <= k; j++) {
        z.push_back(a ^ (a - j));
      }
      q[top][z]++;
    }
  } else {
    cin >> n >> k >> c;
    for (int i = 0; i < n; i++) {
      int a;
      cin >> a;
      int top = __builtin_ctz(a >> 4);
      base ^= a;
      vector<int> z;
      for (int j = 0; j <= k; j++) {
        z.push_back(a ^ (a - j));
      }
      q[top][z]++;
    }
  }
  using block = vector<vector<pair<int, num> > >;
  vector<pair<int, block> > rets;
  for (auto stuff : q) {
    vector<block> ints;
    for (auto xors : stuff.second) {
      int freq = xors.second;
      assert(xors.first.size() == k + 1);
      map<int, num> dp[17][17];
      dp[0][0][0] = 1;
      for (int len = 1; len <= k; len++) {
        for (int pdis = k; pdis >= 0; pdis--) {
          for (int a = 1; a * len <= k && pdis + a <= k; a++) {
            num mult = ifact[a];
            for (int _ = 0; _ < a; _++) mult *= ifact[len];
            for (int psum = 0; psum + a * len <= k; psum++) {
              for (auto g : dp[pdis][psum]) {
                int ndis = pdis + a;
                int nsum = psum + a * len;
                int nval = g.first;
                if (a & 1) nval ^= xors.first[len];
                dp[ndis][nsum][nval] += g.second * mult;
              }
            }
          }
        }
      }
      vector<map<int, num> > dels(17);
      for (int dis = 0; dis <= k; dis++) {
        for (int v = 0; v <= k; v++) {
          for (auto g : dp[dis][v]) {
            num cnt = g.second;
            cnt *= ncr(freq, dis) * fact[dis] * fact[v];
            dels[v][g.first] += cnt;
          }
        }
      }
      vector<vector<pair<int, num> > > del(17);
      for (int v = 0; v <= k; v++) {
        for (auto g : dels[v]) {
          del[v].push_back(g);
        }
      }
      ints.push_back(del);
    }
    vector<map<int, num> > dels(17);
    dels[0][0] += 1;
    for (block del : ints) {
      vector<map<int, num> > newdels(17);
      for (int i = 0; i <= k; i++) {
        for (int j = 0; i + j <= k; j++) {
          for (auto f : dels[i]) {
            for (auto g : del[j]) {
              newdels[i + j][f.first ^ g.first] +=
                  ncr(i + j, i) * f.second * g.second;
            }
          }
        }
      }
      dels = newdels;
    }
    vector<vector<pair<int, num> > > del(17);
    int key = 0;
    for (int v = 0; v <= k; v++) {
      for (auto g : dels[v]) {
        del[v].push_back(g);
        key = max(key, g.first);
      }
    }
    int z = 1;
    while (z <= key) z *= 2;
    rets.push_back({z, del});
  }
  vector<vector<num> > ans(k + 1, vector<num>(1 << c, 0));
  ans[0][0] = 1;
  for (auto ret : rets) {
    block del = ret.second;
    vector<vector<num> > nans(k + 1, vector<num>(1 << c, 0));
    for (int oldv = 0; oldv <= k; oldv++) {
      for (int v = 0; v + oldv <= k; v++) {
        for (auto g : del[v]) {
          num cnt = g.second;
          cnt *= ncr(k - oldv, v);
          for (int j = 0; j < 1 << c; j++) {
            nans[v + oldv][j ^ g.first] += ans[oldv][j] * cnt;
          }
        }
      }
    }
    ans = nans;
  }
  num tot = 0;
  for (int j = 0; j < (1 << c); j++) {
    tot += ans[k][j];
  }
  num den = 1 / pow(num(n), k);
  for (int j = 0; j < (1 << c); j++) {
    cout << ans[k][base ^ j] * den << ' ';
  }
  cout << '\n';
}

### Prompt

Generate a CPP solution to the following problem:

You are given a positive integer k and an array a_1, a_2, …, a_n of non-negative distinct integers not smaller than k and not greater than 2^c-1.

In each of the next k seconds, one element is chosen randomly equiprobably out of all n elements and decreased by 1.

For each integer x, 0 ≤ x ≤ 2^c - 1, you need to find the probability that in the end the bitwise XOR of all elements of the array is equal to x. 

Each of these values can be represented as an irreducible fraction p/q, and you need to find the value of p ⋅ q^{-1} modulo 998 244 353. 

Input

The first line of input contains three integers n, k, c (1 ≤ n ≤ (2^c - k), 1 ≤ k ≤ 16, 1 ≤ c ≤ 16).

The second line contains n distinct integers a_1, a_2, …, a_n (k ≤ a_i ≤ 2^c-1).

Output

Print 2^c integers: the probability that the bitwise XOR is equal to x in the end for x in \{0, 1, …, 2^c-1\} modulo 998 244 353.

Example

Input


4 1 3
1 2 3 4


Output


0 0 0 748683265 0 499122177 0 748683265 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <int MOD_>
struct modnum {
  static constexpr int MOD = MOD_;
  static_assert(MOD_ > 0, "MOD must be positive");

 private:
  using ll = long long;
  int v;
  static int minv(int a, int m) {
    a %= m;
    assert(a);
    return a == 1 ? 1 : int(m - ll(minv(m, a)) * ll(m) / a);
  }

 public:
  modnum() : v(0) {}
  modnum(ll v_) : v(int(v_ % MOD)) {
    if (v < 0) v += MOD;
  }
  explicit operator int() const { return v; }
  friend std::ostream& operator<<(std::ostream& out, const modnum& n) {
    return out << int(n);
  }
  friend std::istream& operator>>(std::istream& in, modnum& n) {
    ll v_;
    in >> v_;
    n = modnum(v_);
    return in;
  }
  friend bool operator==(const modnum& a, const modnum& b) {
    return a.v == b.v;
  }
  friend bool operator!=(const modnum& a, const modnum& b) {
    return a.v != b.v;
  }
  modnum inv() const {
    modnum res;
    res.v = minv(v, MOD);
    return res;
  }
  friend modnum inv(const modnum& m) { return m.inv(); }
  modnum neg() const {
    modnum res;
    res.v = v ? MOD - v : 0;
    return res;
  }
  friend modnum neg(const modnum& m) { return m.neg(); }
  modnum operator-() const { return neg(); }
  modnum operator+() const { return modnum(*this); }
  modnum& operator++() {
    v++;
    if (v == MOD) v = 0;
    return *this;
  }
  modnum& operator--() {
    if (v == 0) v = MOD;
    v--;
    return *this;
  }
  modnum& operator+=(const modnum& o) {
    v += o.v;
    if (v >= MOD) v -= MOD;
    return *this;
  }
  modnum& operator-=(const modnum& o) {
    v -= o.v;
    if (v < 0) v += MOD;
    return *this;
  }
  modnum& operator*=(const modnum& o) {
    v = int(ll(v) * ll(o.v) % MOD);
    return *this;
  }
  modnum& operator/=(const modnum& o) { return *this *= o.inv(); }
  friend modnum operator++(modnum& a, int) {
    modnum r = a;
    ++a;
    return r;
  }
  friend modnum operator--(modnum& a, int) {
    modnum r = a;
    --a;
    return r;
  }
  friend modnum operator+(const modnum& a, const modnum& b) {
    return modnum(a) += b;
  }
  friend modnum operator-(const modnum& a, const modnum& b) {
    return modnum(a) -= b;
  }
  friend modnum operator*(const modnum& a, const modnum& b) {
    return modnum(a) *= b;
  }
  friend modnum operator/(const modnum& a, const modnum& b) {
    return modnum(a) /= b;
  }
};
template <typename T>
T pow(T a, long long b) {
  assert(b >= 0);
  T r = 1;
  while (b) {
    if (b & 1) r *= a;
    b >>= 1;
    a *= a;
  }
  return r;
}
using num = modnum<998244353>;
vector<num> fact, ifact;
void init() {
  int N = 110000;
  fact = {1};
  for (int i = 1; i < N; i++) fact.push_back(i * fact[i - 1]);
  ifact.resize(N);
  ifact.back() = 1 / fact.back();
  for (int i = N - 1; i > 0; i--) ifact[i - 1] = i * ifact[i];
}
num ncr(int n, int k) {
  if (k < 0 || k > n) return 0;
  return fact[n] * ifact[k] * ifact[n - k];
}
int main() {
  ios_base::sync_with_stdio(false), cin.tie(nullptr);
  init();
  int base = 0;
  int n, k, c;
  map<int, map<vector<int>, int> > q;
  if (0) {
    c = k = 16;
    n = (1 << c) - k;
    for (int a = k; a < (1 << c); a++) {
      int top = __builtin_ctz(a >> 4);
      base ^= a;
      vector<int> z;
      for (int j = 0; j <= k; j++) {
        z.push_back(a ^ (a - j));
      }
      q[top][z]++;
    }
  } else {
    cin >> n >> k >> c;
    for (int i = 0; i < n; i++) {
      int a;
      cin >> a;
      int top = __builtin_ctz(a >> 4);
      base ^= a;
      vector<int> z;
      for (int j = 0; j <= k; j++) {
        z.push_back(a ^ (a - j));
      }
      q[top][z]++;
    }
  }
  using block = vector<vector<pair<int, num> > >;
  vector<pair<int, block> > rets;
  for (auto stuff : q) {
    vector<block> ints;
    for (auto xors : stuff.second) {
      int freq = xors.second;
      assert(xors.first.size() == k + 1);
      map<int, num> dp[17][17];
      dp[0][0][0] = 1;
      for (int len = 1; len <= k; len++) {
        for (int pdis = k; pdis >= 0; pdis--) {
          for (int a = 1; a * len <= k && pdis + a <= k; a++) {
            num mult = ifact[a];
            for (int _ = 0; _ < a; _++) mult *= ifact[len];
            for (int psum = 0; psum + a * len <= k; psum++) {
              for (auto g : dp[pdis][psum]) {
                int ndis = pdis + a;
                int nsum = psum + a * len;
                int nval = g.first;
                if (a & 1) nval ^= xors.first[len];
                dp[ndis][nsum][nval] += g.second * mult;
              }
            }
          }
        }
      }
      vector<map<int, num> > dels(17);
      for (int dis = 0; dis <= k; dis++) {
        for (int v = 0; v <= k; v++) {
          for (auto g : dp[dis][v]) {
            num cnt = g.second;
            cnt *= ncr(freq, dis) * fact[dis] * fact[v];
            dels[v][g.first] += cnt;
          }
        }
      }
      vector<vector<pair<int, num> > > del(17);
      for (int v = 0; v <= k; v++) {
        for (auto g : dels[v]) {
          del[v].push_back(g);
        }
      }
      ints.push_back(del);
    }
    vector<map<int, num> > dels(17);
    dels[0][0] += 1;
    for (block del : ints) {
      vector<map<int, num> > newdels(17);
      for (int i = 0; i <= k; i++) {
        for (int j = 0; i + j <= k; j++) {
          for (auto f : dels[i]) {
            for (auto g : del[j]) {
              newdels[i + j][f.first ^ g.first] +=
                  ncr(i + j, i) * f.second * g.second;
            }
          }
        }
      }
      dels = newdels;
    }
    vector<vector<pair<int, num> > > del(17);
    int key = 0;
    for (int v = 0; v <= k; v++) {
      for (auto g : dels[v]) {
        del[v].push_back(g);
        key = max(key, g.first);
      }
    }
    int z = 1;
    while (z <= key) z *= 2;
    rets.push_back({z, del});
  }
  vector<vector<num> > ans(k + 1, vector<num>(1 << c, 0));
  ans[0][0] = 1;
  for (auto ret : rets) {
    block del = ret.second;
    vector<vector<num> > nans(k + 1, vector<num>(1 << c, 0));
    for (int oldv = 0; oldv <= k; oldv++) {
      for (int v = 0; v + oldv <= k; v++) {
        for (auto g : del[v]) {
          num cnt = g.second;
          cnt *= ncr(k - oldv, v);
          for (int j = 0; j < 1 << c; j++) {
            nans[v + oldv][j ^ g.first] += ans[oldv][j] * cnt;
          }
        }
      }
    }
    ans = nans;
  }
  num tot = 0;
  for (int j = 0; j < (1 << c); j++) {
    tot += ans[k][j];
  }
  num den = 1 / pow(num(n), k);
  for (int j = 0; j < (1 << c); j++) {
    cout << ans[k][base ^ j] * den << ' ';
  }
  cout << '\n';
}

```