Palindrome Addition

For an integer $M \ge 2$, let $\mathbb{Z}/M\mathbb{Z}$ denote the residue classes modulo $M$. In this problem, every residue is represented by one of $0,1,\cdots,M-1$.

A nonzero polynomial of degree $d$,

is called a palindromic polynomial if $a_i=a_{d-i}$ for every $0\le i\le d$. The zero polynomial is not considered palindromic.

You are given a nonzero polynomial over $\mathbb{Z}/M\mathbb{Z}$,

Construct an integer $K$ with $1\le K\le3$ and palindromic polynomials $P_1,P_2,\cdots,P_K$ such that

All coefficient additions are performed modulo $M$.

The input is given from Standard Input in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

Each case is given in the following format:

$M\ N$ $c_0\ c_1\ \cdots\ c_N$

Here $M$ is the modulus for the coefficients and $N$ is the degree of the input polynomial. The coefficients are given from the constant term to the leading term.

For each test case, first print the number $K$ of palindromic polynomials used.

Then print $K$ lines. For the $j$-th palindromic polynomial

print one line in the following format:

$d_j\ a_{j,0}\ a_{j,1}\ \cdots\ a_{j,d_j}$

The output must satisfy all of the following conditions.

• $1\le K\le3$.
• $0\le d_j\le N$ for every $1\le j\le K$.
• $0\le a_{j,i}<M$ for every $1\le j\le K$ and $0\le i\le d_j$.
• $a_{j,d_j}\ne0$ for every $1\le j\le K$.
• Every $P_j$ is palindromic.
• For every $0\le i\le N$, treating the coefficient of $x^i$ in $P_j$ as $0$ when $d_j<i$, the coefficient of $x^i$ in $P_1+P_2+\cdots+P_K$ is congruent to $c_i$ modulo $M$.

If there are multiple valid outputs, print any of them. Do not print any separator between test cases.

• $1\le T\le300\,000$.
• $2\le M\le1\,000\,000\,000$.
• $0\le N\le200\,000$.
• $0\le c_i<M$ for every $0\le i\le N$.
• $c_N\ne0$.
• Over all test cases, $\sum (N+1)\le300\,000$.