E. Polynomial Equation
time limit per test
1.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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]$$$$$$^{\text{∗}}$$$,
  • $$$\deg S \leq d$$$.
If a solution exists, output any valid $$$Q, R$$$. Note that you do not need to output $$$S$$$.

$$$^{\text{∗}}$$$i.e. when expanded, the two sides of the equation have equal coefficients modulo $$$p$$$.

Input

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 \lt 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} \lt 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$$$.

Output

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 \lt 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 \lt 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$$$.

You can output "YES" and "NO" in any case (for example, strings "yES", "yes" and "Yes" will be recognized as a positive response).

Scoring

There are five subtasks for this problem.

  • ($$$5$$$ points): The sum of $$$n$$$ across all test cases is no more than $$$10$$$, and $$$d = -1$$$, i.e. we constrain that $$$S$$$ is the zero polynomial.
  • ($$$5$$$ points): $$$d = n - 1$$$.
  • ($$$30$$$ points): $$$d = -1$$$, i.e. we constrain that $$$S$$$ is the zero polynomial.
  • ($$$30$$$ points): The sum of $$$n$$$ across all test cases is no more than $$$500$$$.
  • ($$$30$$$ points): No additional constraints.
Example
Input
5
2 -1
40 9 13
9 0
13
4 2
1000000000 1 1000000001 2 1
1 1000000000 2 0
999999999 2 1
2 0
1
4 2
1000000000 1 1000000001 2 1
1 1000000000 1 0
999999999 1 1
2 0
1
4 2
120 50 61 235 169
50 81 119 0
61 119 169
235 0
169
9 5
17 18 19 20 21 22 2 6 0 1
16 8 8 4 8 0 2 0 0
15 8 0 4 0 0 0 0
14 4 4 2 4 0 1
13 8 0 4 0 0
12 0 0 0 0
2 2 0 1
6 0 0
0 0
1
Output
YES
2 4
20 9 13
400 360 601 234 169
NO
YES
2 6
1 1 1
2 4 7 7 6 3 1
NO
YES
3 12
0 2 0 1
0 0 0 16 16 24 32 12 24 2 8 0 1
Note

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.