팰린드롬 덧셈

정수 $M \ge 2$에 대하여 $\mathbb{Z}/M\mathbb{Z}$를 $M$을 법으로 하는 나머지류의 집합이라 하자. 이 문제에서는 각 원소를 $0,1,\cdots,M-1$ 중 하나로 나타낸다.

차수가 $d$인 0이 아닌 다항식

이 모든 $0\le i\le d$에 대하여 $a_i=a_{d-i}$를 만족하면, $P$를 팰린드롬 다항식이라고 한다. 0 다항식은 팰린드롬 다항식으로 보지 않는다.

$\mathbb{Z}/M\mathbb{Z}$ 위의 0이 아닌 다항식

이 주어진다. $1\le K\le3$인 정수 $K$와 팰린드롬 다항식 $P_1,P_2,\cdots,P_K$를 하나 구성하여

가 성립하게 하여라. 모든 계수의 덧셈은 $M$을 법으로 한다.

입력은 다음과 같은 형식으로 주어진다.

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

각 케이스는 다음과 같은 형식으로 주어진다.

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

$M$은 계수의 법이고, $N$은 입력 다항식의 차수이다. 계수는 상수항부터 최고차항까지의 순서로 주어진다.

각 테스트 케이스마다 먼저 사용할 팰린드롬 다항식의 개수 $K$를 한 줄에 출력한다.

그 다음 $K$개의 줄에 걸쳐 $j$번째 팰린드롬 다항식

을 다음과 같은 형식으로 출력한다.

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

출력은 다음 조건을 모두 만족해야 한다.

• $1\le K\le3$.
• $0\le d_j\le N$ ($1\le j\le K$).
• $0\le a_{j,i}<M$ ($1\le j\le K$, $0\le i\le d_j$).
• $a_{j,d_j}\ne0$ ($1\le j\le K$).
• 각 $P_j$는 팰린드롬 다항식이다.
• 각 $0\le i\le N$에 대하여, $d_j<i$이면 $P_j$의 $x^i$의 계수를 $0$으로 보았을 때 $P_1+P_2+\cdots+P_K$의 $x^i$의 계수가 $c_i$와 $M$을 법으로 같다.

가능한 출력이 여러 가지라면 아무거나 출력해도 된다. 테스트 케이스 사이에 별도의 구분자는 출력하지 않는다.

• $1\le T\le300\,000$.
• $2\le M\le1\,000\,000\,000$.
• $0\le N\le200\,000$.
• $0\le c_i<M$ ($0\le i\le N$).
• $c_N\ne0$.
• 모든 테스트 케이스에 대한 $\sum (N+1)\le300\,000$.