Busy Beaver 有一个他不知道如何求解的多项式方程，他需要你的帮助！

对于二元多项式 $P(x, y) = \sum_{i,j \ge 0} a_{i,j} x^i y^j$，定义其次数 $\deg P = \max_{a_{i,j} \neq 0} (i + j)$。例如，$\deg(x + y + xy) = 2$。此外，我们规定零多项式的次数 $\deg 0 = -1$。

给定一个具有整数系数的二元多项式 $P(x, y)$ 和一个整数 $d \ge -1$，确定是否存在一个二元多项式 $S(x, y)$ 和非常数一元多项式 $Q, R$，使得：

• 对于 $p = 10^9 + 7$，满足 $$(P(x, y) + S(x, y))(Q(x) - Q(y)) = R(x) - R(y)$$ 作为 $\mathbb{F}_p[x, y]^*$ 中的多项式，
• $\deg S \le d$。

如果存在解，输出任意一组有效的 $Q, R$。注意，你不需要输出 $S$。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $T$ ($1 \le T \le 100$)。

接下来是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n, d$ ($1 \le n \le 2.5 \cdot 10^3, -1 \le d < n$)，分别表示 $\deg P$ 的值和 $\deg S$ 的上界。

接下来的 $n+1$ 行中，第 $i$ 行包含 $n+2-i$ 个整数 $a_{i-1,0}, \dots, a_{i-1,n+1-i}$ ($0 \le a_{i,j} < 10^9 + 7$)，即 $P$ 的系数，使得 $P(x, y) = \sum_{i,j \ge 0, i+j \le n} a_{i,j} x^i y^j$。保证 $P$ 的次数为 $n$，即 $a_{0,n}, a_{1,n-1}, \dots, a_{n,0}$ 中至少有一个非零。

保证所有测试用例中 $n$ 的总和不超过 $2.5 \cdot 10^3$。

输出格式

如果存在解，每个测试用例输出的第一行应包含字符串 “YES”（不含引号），否则输出 “NO”（不含引号）。

如果你声称存在解，请继续按以下格式输出解：

每个测试用例输出的第二行应包含两个整数 $q, r$ ($1 \le q, r \le 5 \cdot 10^3$)，分别为多项式 $Q, R$ 的次数。

每个测试用例输出的第三行应包含 $q+1$ 个整数 $b_0, \dots, b_q$ ($0 \le b_i < 10^9 + 7, b_q \neq 0$)，即 $Q(t) = \sum_{i=0}^q b_i t^i$ 的系数。

每个测试用例输出的第四行应包含 $r+1$ 个整数 $c_0, \dots, c_r$ ($0 \le c_i < 10^9 + 7, c_r \neq 0$)，即 $R(t) = \sum_{i=0}^r c_i t^i$ 的系数。

注意，你不需要输出 $S$ —— 裁判程序将确定是否存在满足你所给出的 $Q, R$ 的 $S$。

你可以以任意大小写形式输出 “YES” 和 “NO”（例如，“yES”、“yes” 和 “Yes” 都会被识别为肯定回答）。

子任务

本题共有五个子任务。

• (5 分)：所有测试用例中 $n$ 的总和不超过 $10$，且 $d = -1$，即我们限制 $S$ 为零多项式。
• (5 分)：$d = n - 1$。
• (30 分)：$d = -1$，即我们限制 $S$ 为零多项式。
• (30 分)：所有测试用例中 $n$ 的总和不超过 $500$。
• (30 分)：无额外限制。

样例

输入 1

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

输出 1

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

说明

在第一个测试用例中，给定的多项式为 $P(x, y) = 13x^2 + 13y^2 + 9x + 9y + 40$。 我们可以取 $S = 0, Q(t) = 13t^2 + 9t + 20, R(t) = (13t^2 + 9t + 20)^2$，这给出了一个有效的解。 在第二个测试用例中，可以证明不存在解。