Problem: The Elements of Harmony are six supernatural artifacts representing subjective aspects of harmony. They are arguably the most powerful force in Equestria. The inside of Elements of Harmony can be seen as a complete graph with n vertices labeled from 0 to n - 1, where n is a power of two, equal to 2m.

<image>

The energy in Elements of Harmony is in constant movement. According to the ancient book, the energy of vertex u in time i (ei[u]) equals to: 

<image>

Here b[] is the transformation coefficient — an array of m + 1 integers and f(u, v) is the number of ones in the binary representation of number (u xor v).

Given the transformation coefficient and the energy distribution at time 0 (e0[]). Help Twilight Sparkle predict the energy distribution at time t (et[]). The answer can be quite large, so output it modulo p.

Input

The first line contains three integers m, t and p (1 ≤ m ≤ 20; 0 ≤ t ≤ 1018; 2 ≤ p ≤ 109). The following line contains n (n = 2m) integers e0[i] (1 ≤ e0[i] ≤ 109; 0 ≤ i < n). The next line contains m + 1 integers b[i] (0 ≤ b[i] ≤ 109; 0 ≤ i ≤ m).

Output

Output n lines, the i-th line must contain a single integer et[i] modulo p.

Examples

Input

2 2 10000
4 1 2 3
0 1 0


Output

14
6
6
14

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
namespace baseFastio {
template <typename Int>
inline Int read() {
  Int flag = 1;
  char c = getchar();
  while ((!isdigit(c)) && c != '-' && c != EOF) c = getchar();
  if (c == '-') flag = -1, c = getchar();
  Int init = c & 15;
  while (isdigit(c = getchar())) init = (init << 3) + (init << 1) + (c & 15);
  return init * flag;
}
template <typename Int>
inline Int read(char& c) {
  Int flag = 1;
  c = getchar();
  while ((!isdigit(c)) && c != '-' && c != EOF) c = getchar();
  if (c == '-') flag = -1, c = getchar();
  Int init = c & 15;
  while (isdigit(c = getchar())) init = (init << 3) + (init << 1) + (c & 15);
  return init * flag;
}
template <typename Int>
inline void write(Int x) {
  if (x < 0) putchar('-'), x = ~x + 1;
  if (x > 9) write(x / 10);
  putchar((x % 10) | 48);
}
template <typename Int>
inline void write(Int x, char nextch) {
  write(x);
  putchar(nextch);
}
}  // namespace baseFastio
namespace Fastio {
enum io_flags { ignore_int = 1 << 0 };
struct Reader {
  char endch;
  Reader() { endch = '\0'; }
  template <typename Int>
  Int operator()() {
    return baseFastio::read<Int>(endch);
    ;
  }
  Reader& operator>>(io_flags f) {
    if (f == ignore_int) baseFastio::read<int>();
    return *this;
  }
  template <typename Int>
  Reader& operator>>(Int& i) {
    i = baseFastio::read<Int>(endch);
    return *this;
  }
  template <typename Int>
  inline Int get_int() {
    return baseFastio::read<Int>();
  }
  inline char get_nxt() { return endch; }
} read;
struct Writer {
  Writer& operator<<(const char* ch) {
    while (*ch) putchar(*(ch++));
    return *this;
  }
  Writer& operator<<(const char ch) {
    putchar(ch);
    return *this;
  }
  template <typename Int>
  Writer& operator<<(const Int i) {
    baseFastio::write(i);
    return *this;
  }
} write;
}  // namespace Fastio
using namespace Fastio;
long long mul(long long a, long long b, long long P) {
  return ((a * b - ((long long)((long double)a / P * b) * P)) % P + P) % P;
}
long long fpow(long long a, long long n, const long long P) {
  long long ret = 1;
  while (n) {
    if (n & 1) ret = mul(ret, a, P);
    a = mul(a, a, P);
    n >>= 1;
  }
  return ret;
}
namespace FWT {
void FWT_XOR(long long* a, int n, long long MUL = 1,
             const long long P = 998244353) {
  for (int s = 2, t = 1; s <= n; s <<= 1, t <<= 1)
    for (int i = 0; i < n; i += s)
      for (int j = 0; j < t; j++) {
        long long a0 = a[i + j], a1 = a[i + j + t];
        a[i + j] = (a0 + a1) % P;
        a[i + j + t] = (a0 - a1 + P) % P;
        a[i + j] = mul(a[i + j], MUL, P);
        a[i + j + t] = mul(a[i + j + t], MUL, P);
      }
}
}  // namespace FWT
namespace against_cpp11 {
const int N = 1.2e6 + 7, M = 20 + 7;
int n, m;
long long t, p;
long long e0[N], b[N];
long long a[N], buf[N];
const int popcount_table[] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};
int popcount(long long u) {
  int ret = 0;
  while (u) {
    ret += popcount_table[u & 15];
    u >>= 4;
  }
  return ret;
}
signed main() {
  read >> m >> t >> p;
  n = (1 << m);
  p *= n;
  for (int i = 0; i < n; i++) read >> e0[i];
  for (int i = 0; i <= m; i++) read >> buf[i];
  for (int i = 0; i < n; i++) b[i] = buf[popcount(i)];
  for (int i = 0; i < n; i++) a[i] = e0[i];
  FWT::FWT_XOR(a, n, 1, p);
  FWT::FWT_XOR(b, n, 1, p);
  while (t) {
    if (t & 1)
      for (int i = 0; i < n; i++) a[i] = mul(a[i], b[i], p);
    for (int i = 0; i < n; i++) b[i] = mul(b[i], b[i], p);
    t >>= 1;
  }
  FWT::FWT_XOR(a, n, 1, p);
  for (int i = 0; i < n; i++) a[i] /= n;
  for (int i = 0; i < n; i++) write << a[i] << '\n';
  return 0;
}
}  // namespace against_cpp11
signed main() { return against_cpp11::main(); }