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 JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.IOException;
import java.io.UncheckedIOException;
import java.io.Closeable;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) throws Exception {
        Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 29);
        thread.start();
        thread.join();
    }

    static class TaskAdapter implements Runnable {
        @Override
        public void run() {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            FastInput in = new FastInput(inputStream);
            FastOutput out = new FastOutput(outputStream);
            DLittlePonyAndElementsOfHarmony solver = new DLittlePonyAndElementsOfHarmony();
            solver.solve(1, in, out);
            out.close();
        }
    }

    static class DLittlePonyAndElementsOfHarmony {
        public void solve(int testNumber, FastInput in, FastOutput out) {
            int m = in.ri();
            long t = in.rl();
            int p = in.ri();
            int n = 1 << m;
            ILongModular mod = ILongModular.getInstance((long) n * p);
            long[] e = new long[n];
            for (int i = 0; i < n; i++) {
                e[i] = in.ri();
            }
            long[] b = new long[m + 1];
            for (int i = 0; i < m + 1; i++) {
                b[i] = in.ri();
            }

            long[] a = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = b[Integer.bitCount(i)];
            }
            LongPower pow = new LongPower(mod);
            FastWalshHadamardTransform.xorFWT(e, n, mod.getMod(), false);
            FastWalshHadamardTransform.xorFWT(a, n, mod.getMod(), false);
            for (int i = 0; i < n; i++) {
                a[i] = pow.pow(a[i], t);
            }
            FastWalshHadamardTransform.dotMul(e, a, e, 0, n - 1, mod);
            FastWalshHadamardTransform.xorFWT(e, n, mod.getMod(), true);
            for (int i = 0; i < n; i++) {
                out.append(e[i] % p).println();
            }
        }

    }

    static interface ILongModular {
        long getMod();

        long mul(long a, long b);

        static ILongModular getInstance(long mod) {
            if (mod <= Integer.MAX_VALUE) {
                return new SmallLongModular(mod);
            }
            if (mod <= (1L << 50)) {
                return new LongModularDanger(mod);
            }
            if (mod == (1L << 61) - 1) {
                return LongModular2305843009213693951.getInstance();
            }
            return new LongModular(mod);//new BigLongModular(mod);//new LongModular(mod);
        }

    }

    static class FastInput {
        private final InputStream is;
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastInput(InputStream is) {
            this.is = is;
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    bufLen = -1;
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }

        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }

        public int ri() {
            return readInt();
        }

        public int readInt() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            int val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

        public long rl() {
            return readLong();
        }

        public long readLong() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            long val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

    }

    static class LongPower {
        final ILongModular modular;

        public LongPower(ILongModular modular) {
            this.modular = modular;
        }

        public long pow(long x, long n) {
            if (n == 0) {
                return 1;
            }
            long r = pow(x, n >> 1);
            r = modular.mul(r, r);
            if ((n & 1) == 1) {
                r = modular.mul(r, x);
            }
            return r;
        }

    }

    static class FastWalshHadamardTransform {
        public static void dotMul(long[] a, long[] b, long[] c, int l, int r, ILongModular mod) {
            for (int i = l; i <= r; i++) {
                c[i] = mod.mul(a[i], b[i]);
            }
        }

        public static void xorFWT(long[] f, int N, long mod, boolean rev) {
            long t1, t2;
            for (int s = 2; s <= N; s <<= 1)
                for (int i = 0, t = s >> 1; i < N; i += s)
                    for (int j = i; j < i + t; j++) {
                        t1 = f[j];
                        t2 = f[j + t];
                        f[j] = (t1 + t2);
                        f[j + t] = (t1 - t2);
                        if (f[j] >= mod) {
                            f[j] -= mod;
                        }
                        if (f[j + t] < 0) {
                            f[j + t] += mod;
                        }
                    }
            if (!rev) return;
            for (int i = 0; i < N; i++) f[i] /= N;
        }

    }

    static class DigitUtils {
        private DigitUtils() {
        }

        public static long round(double x) {
            if (x >= 0) {
                return (long) (x + 0.5);
            } else {
                return (long) (x - 0.5);
            }
        }

        public static long mod(long x, long mod) {
            if (x < -mod || x >= mod) {
                x %= mod;
            }
            if (x < 0) {
                x += mod;
            }
            return x;
        }

        public static long modmul(long a, long b, long mod) {
            long k = DigitUtils.round((double) a / mod * b);
            return DigitUtils.mod(a * b - k * mod, mod);
        }

    }

    static class FastOutput implements AutoCloseable, Closeable, Appendable {
        private static final int THRESHOLD = 32 << 10;
        private final Writer os;
        private StringBuilder cache = new StringBuilder(THRESHOLD * 2);

        public FastOutput append(CharSequence csq) {
            cache.append(csq);
            return this;
        }

        public FastOutput append(CharSequence csq, int start, int end) {
            cache.append(csq, start, end);
            return this;
        }

        private void afterWrite() {
            if (cache.length() < THRESHOLD) {
                return;
            }
            flush();
        }

        public FastOutput(Writer os) {
            this.os = os;
        }

        public FastOutput(OutputStream os) {
            this(new OutputStreamWriter(os));
        }

        public FastOutput append(char c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput append(long c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput append(String c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput println() {
            return append(System.lineSeparator());
        }

        public FastOutput flush() {
            try {
//            boolean success = false;
//            if (stringBuilderValueField != null) {
//                try {
//                    char[] value = (char[]) stringBuilderValueField.get(cache);
//                    os.write(value, 0, cache.length());
//                    success = true;
//                } catch (Exception e) {
//                }
//            }
//            if (!success) {
                os.append(cache);
//            }
                os.flush();
                cache.setLength(0);
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
            return this;
        }

        public void close() {
            flush();
            try {
                os.close();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }

        public String toString() {
            return cache.toString();
        }

    }

    static class LongModular implements ILongModular {
        final long m;

        public long getMod() {
            return m;
        }

        public LongModular(long m) {
            this.m = m;
        }

        public long mul(long a, long b) {
            if (b == 0) {
                return 0;
            }
            long ans = mul(a, b >> 1) << 1;
            if (ans >= m) {
                ans -= m;
            }
            ans += a * (b & 1);
            if (ans >= m) {
                ans -= m;
            }
            return ans;
        }

    }

    static class LongModular2305843009213693951 implements ILongModular {
        private static long mod = 2305843009213693951L;
        private static final LongModular2305843009213693951 INSTANCE = new LongModular2305843009213693951();
        private static long mask = (1L << 32) - 1;

        private LongModular2305843009213693951() {
        }

        public static final LongModular2305843009213693951 getInstance() {
            return INSTANCE;
        }

        public long getMod() {
            return mod;
        }

        public long mul(long a, long b) {
            long l1 = a & mask;
            long h1 = (a >> 32) & mask;
            long l2 = b & mask;
            long h2 = (b >> 32) & mask;
            long l = l1 * l2;
            long m = l1 * h2 + l2 * h1;
            long h = h1 * h2;
            long ret = (l & mod) + (l >>> 61) + (h << 3) + (m >>> 29) + ((m << 35) >>> 3) + 1;
            ret = (ret & mod) + (ret >>> 61);
            ret = (ret & mod) + (ret >>> 61);
            return ret - 1;
        }

    }

    static class SmallLongModular implements ILongModular {
        long mod;

        public SmallLongModular(long mod) {
            this.mod = mod;
        }

        public long getMod() {
            return mod;
        }

        public long mul(long a, long b) {
            return a * b % mod;
        }

    }

    static class LongModularDanger implements ILongModular {
        final long m;

        public long getMod() {
            return m;
        }

        public LongModularDanger(long m) {
            this.m = m;
        }

        public long mul(long a, long b) {
            return DigitUtils.modmul(a, b, m);
        }

    }
}