#include "NTL/ZZXFactoring.h"
#include "NTL/ZZ_p.h"
#include "NTL/vec_ZZ.h"
#include <ctime>
#include <cstdio>
#include <vector>
#include <cassert>

using namespace std;
using namespace NTL;

long long n, k;
vector<vector<ZZ_pX> > P;
vec_ZZ_p v, v2;
vector<ZZ_p> si, vhat_i;

vector<ZZ_p> myeval(ZZ_pX& poly, long long start, long long end, long long k) {
	if (end - start == 0) {
		vector<ZZ_p> val;
		ZZ_p evalresult;
		eval(evalresult, poly, v2[start]);
		val.push_back(evalresult);
		return val;
	}
	int jump = (1LL << (k - 1));
	int index = start / jump;
	ZZ_pX r0 = poly % P[k-1][index];
	ZZ_pX r1 = poly % P[k-1][index+1];
	vector<ZZ_p> res1 = myeval(r0, start, (start + end) / 2, k-1);
	vector<ZZ_p> res2 = myeval(r1, (start + end) / 2 + 1, end, k-1);
	for (int i = 0; i < res2.size(); i++) {
		res1.push_back(res2[i]);
	}
	return res1;
}

ZZ_pX myinterpolation(long long start, long long end, long long k) {
	if (end == start) {
		ZZ_pX result(0, vhat_i[start]);
		return result;
	}
	ZZ_pX r0 = myinterpolation(start, (start + end) / 2, k - 1);
	ZZ_pX r1 = myinterpolation((start + end) / 2 + 1, end, k - 1);
	int jump = (1LL << (k - 1));
	int index = start / jump;
	return (r0 * P[k-1][index + 1]) + (r1 * P[k-1][index]);
}

ZZ_pX VDagger, WDagger;
ZZ_pX f;
ZZ p;
ZZ_pX polyresult;
vec_ZZ_p result;
ZZ_pX Zx, Hx;

int main()
{
	cin >> p;
	ZZ_p::init(p);
	int m;
	cin >> m;
	cin >> v;
	long long reallength = v.length();
	k = NextPowerOfTwo(v.length());
	n = 1LL << k;
	cout << n << endl;
	v.SetLength(n);
	v2.SetLength(n);
	for (int j = 0; j < v.length(); j++) {
		ZZ_p temp;
		temp = j+1;
		v2[j] = temp;
	}
	P.resize(k + 1, vector<ZZ_pX>());
	clock_t beginZx = clock();
	for (int i = 0; i <= k; i++) {
		for (int j = 0; j < (1LL << (k - i)); j++) {
			if (i == 0) {
				ZZ_pX temp(1, 1);
				temp += -v2[j];
				P[i].push_back(temp);
			} else {
				ZZ_pX temp = P[i-1][j << 1] * P[i-1][(j << 1)+1];
				P[i].push_back(temp);
			}
		}
	}
	clock_t endZx = clock();
	ZZ_pX derivative;
	for (int i = 1; i < P[k][0].rep.length(); i++) {
		ZZ_p temp = coeff(P[k][0], i) * i;
		SetCoeff(derivative, i - 1, temp);
	}
	si = myeval(derivative, 0, deg(derivative), k);
	vhat_i.clear();
	clock_t begin = clock();
	for (int i = 0; i < n; i++) {
		vhat_i.push_back(v[i] / si[i]);
	}
	polyresult = myinterpolation(0, n-1, k);
	VDagger = polyresult;
	cerr << "Time to interpolate 1 vector: ";
	cerr << (double(clock()-begin)/CLOCKS_PER_SEC);
	cerr << " sec(s)" << endl;
	result = VectorCopy(polyresult, polyresult.rep.length());
	assert(polyresult.rep.length() == n);
	for (int j = polyresult.rep.length() - 1; j >= 0; j--) {
		cout << result[j] << " ";
	}
	cout << endl;

	for (int i = 1; i < m; i++) {
		cin >> v;
		v.SetLength(n);
		vhat_i.clear();
		for (int j = 0; j < n; j++) {
			vhat_i.push_back(v[j] / si[j]);
		}
		polyresult = myinterpolation(0, n-1, k);
		assert(polyresult.rep.length() == n);
		result = VectorCopy(polyresult, polyresult.rep.length());
		for (int j = polyresult.rep.length() - 1; j >= 0; j--) {
			cout << result[j] << " ";
		}
		cout << endl;
	}

	for (int i = 0; i < m; i++) {
		cin >> v;
		v.SetLength(n);
		vhat_i.clear();
		for (int j = 0; j < n; j++) {
			vhat_i.push_back(v[j] / si[j]);
		}
		polyresult = myinterpolation(0, n-1, k);
		assert(polyresult.rep.length() == n);
		WDagger = polyresult;
		result = VectorCopy(polyresult, polyresult.rep.length());
		for (int j = polyresult.rep.length() - 1; j >= 0; j--) {
			cout << result[j] << " ";
		}
		cout << endl;
	}

	double CRStime = double(clock()-begin)/CLOCKS_PER_SEC;
	begin = clock();
	for (int i = 0; i < 2; i++) {
		cin >> v;
		v.SetLength(n);
		vhat_i.clear();
		for (int j = 0; j < n; j++) {
			vhat_i.push_back(v[j] / si[j]);
		}
		polyresult = myinterpolation(0, n-1, k);
		assert(polyresult.rep.length() == n);
		if (i == 0) {
			VDagger += polyresult;
		} else {
			WDagger += polyresult;
		}
		result = VectorCopy(polyresult, polyresult.rep.length());
		for (int j = polyresult.rep.length() - 1; j >= 0; j--) {
			cout << result[j] << " ";
		}
		cout << endl;
	}
	double proverInterpolateTime = double(clock()-begin)/CLOCKS_PER_SEC;
	begin = clock();
	Zx = P[k][0];
	assert(Zx.rep.length() == n+1);
	Hx = (VDagger * WDagger) / Zx;
	assert(Hx.rep.length() == n-1);
	result = VectorCopy(Hx, Hx.rep.length());
	for (int j = Hx.rep.length() - 1; j >= 0; j--) {
		cout << result[j] << " ";
	}
	cout << endl;
	double proverComputeTime = double(clock()-begin)/CLOCKS_PER_SEC;
	printf("%.3f\n", proverInterpolateTime);
	printf("%.3f\n", proverComputeTime + (double)(endZx - beginZx)/CLOCKS_PER_SEC);
	printf("%.3f\n", CRStime);
}