Polynomial Equation

Busy Beaver has a polynomial equation that he doesn't know how to solve, and he needs your help!

For a bivariate polynomial $P(x,y)=\sum\limits_{i,j \ge 0}a_{i,j}x^iy^j$, define its degree $\deg P = \max\limits_{a_{i,j}\neq 0}(i+j)$. For example, $\deg (x + y + xy) = 2$. Furthermore, we take the degree of the zero polynomial $\deg 0$ to be $-1$.

Given a bivariate polynomial $P(x,y)$ with integer coefficients and an integer $d \geq -1$, determine whether there exists a bivariate polynomial $S(x, y)$ and non-constant univariate polynomials $Q, R$ such that

• for $p = 10^9 + 7$, we have $$(P(x, y) + S(x, y))(Q(x) - Q(y)) = R(x) - R(y)$$ as polynomials in $\mathbb F_p[x, y]$1,
• $\deg S \leq d$.

If a solution exists, output any valid $Q, R$. Note that you do not need to output $S$.

---

1i.e. when expanded, the two sides of the equation have equal coefficients modulo $p$.

Each test contains multiple test cases. The first line contains the number of test cases $T$ ($1 \leq T \leq 100$). The description of the test cases follows.

The first line of each test case contains two integers $n, d$ ($1 \leq n \leq 2.5 \cdot 10^3$, $-1 \leq d < n$) --- the value of $\deg P$ and the upper bound on $\deg S$, respectively.

The $i$-th of the next $n + 1$ lines contains $n + 2 - i$ integers $a_{i-1, 0}, \dots, a_{i-1, n+1-i}$ ($0 \leq a_{i,j} < 10^9 + 7$) --- the coefficients of $P$ so that $P(x,y)=\sum\limits_{i,j \ge 0, i+j \leq n}a_{i,j}x^iy^j$. It is guaranteed that $P$ has degree $n$, i.e. at least one of $a_{0,n}, a_{1,n-1}, \dots, a_{n,0}$ is nonzero.

It is guaranteed that the sum of $n$ across all test cases is no more than $2.5 \cdot 10^3$.

The first line of output for each test case should contain the string "YES" (without quotes) if a solution exists, and "NO" (without quotes) otherwise.

If you claim that a solution exists, continue outputting the solution as follows:

The second line of output for each test case should contain three integers $q, r$ ($1 \leq q, r \leq 5 \cdot 10^3$) --- the degrees of the polynomials $Q, R$ respectively.

The third line of output for each test case should contain $q + 1$ integers $b_0, \dots, b_q$ ($0 \leq b_i < 10^9 + 7$, $b_q \neq 0$) --- the coefficients of $Q(t) = \sum_{i=0}^q b_i t^i$.

The fourth line of output for each test case should contain $r + 1$ integers $c_0, \dots, c_r$ ($0 \leq c_i < 10^9 + 7$, $c_r \neq 0$) --- the coefficients of $R(t) = \sum_{i=0}^r c_i t^i$.

Note that you do not need to output $S$ --- the judge will determine if a suitable choice of $S$ exists for your claimed $Q, R$.

In the first test case, the given polynomial is $$P(x, y) = 13x^2 + 13y^2 + 9x + 9y + 40.$$ We can take $S = 0$, $Q(t) = 13t^2 + 9t + 20$, $R(t) = (13t^2 + 9t + 20)^2$, which gives a valid solution.

In the second test case, it can be shown that no solution exists.