OI XXV - wie

// https://szkopul.edu.pl/problemset/problem/9JvSAnyf5d1FlPAEXEdUAtCz/site/?key=statement

#include <bits/stdc++.h>

// #define GARY_DBG
#define GARY_LIB

constexpr int sizik = 1000 * 1001;

#define ar std::array

typedef std::vector<std::vector<int>> _kra;

int64_t power(int64_t base, int64_t exp, int64_t mod) {
    int64_t res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return res;
}

void forward_ntt(std::vector<int64_t>& a, int n, int64_t q, int64_t m) {
    for (int i = 1, j = 0; i < n; i++) {
        int bit = n >> 1;
        for (; j & bit; bit >>= 1)
            j ^= bit;
        j ^= bit;
        if (i < j) std::swap(a[i], a[j]);
    }

    int64_t w_half = power(q, n / 2, m);

    for (int len = 2; len <= n; len <<= 1) {
        int64_t wlen = power(q, n / len, m);

        for (int i = 0; i < n; i += len) {
            int64_t w = 1;
            for (int j = 0; j < len / 2; j++) {
                int64_t u = a[i + j];
                int64_t odd_val = a[i + j + len / 2];

                int64_t v1 = (odd_val * w) % m;
                int64_t v2 = (v1 * w_half) % m;

                a[i + j] = (u + v1 >= m ? u + v1 - m : u + v1);
                a[i + j + len / 2] = (u + v2 >= m ? u + v2 - m : u + v2);

                w = (w * wlen) % m;
            }
        }
    }
}

void solve() {
    int n;
    int64_t m, q;
    std::cin >> n >> m >> q;

    std::vector<int64_t> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        a[i] %= m;
    }

    forward_ntt(a, n, q, m);

    int64_t sum_val = 0;
    for (int i = 0; i < n; i++) {
        sum_val += a[i];
        if (sum_val >= m) sum_val -= m;
    }
    std::cout << sum_val << "\n";

    for (int i = 1; i < n; i++) {
        std::cout << a[i] << " ";
    }
    std::cout << a[0] << "\n";
}

int32_t main() {
#ifndef GARY_DBG
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
#endif

    int t = 1;
    // std::cin >> t;

    for (; t > 0; t--) {
        solve();
    }

    return 0;
}