回文多项式是一个非零多项式，其系数从两端读起完全相同。 Alan 曾有一个次数为 $d \le 10^4$ 的回文多项式 $A$。他在 $n$ 个不同的整数点上记录了该多项式模 $10^9 + 9$ 的值。后来他丢失了这个多项式。现在他想根据这些点恢复它。请帮助 Alan 找到任意一个次数不超过 $10^4$ 且经过所有给定点的回文多项式。

形式化地，给定一组点对 $(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$，其中 $0 \le x_i, y_i < 10^9 + 9$。你的任务是找到任意一个多项式 $A(x) = a_d x^d + a_{d-1} x^{d-1} + \dots + a_1 x + a_0$，使得：

• $0 \le d \le 10^4$ 且 $a_d \neq 0$；
• 对于 $i = 0 \dots d$，满足 $0 \le a_i < 10^9 + 9$；
• 对于 $i = 1 \dots n$，满足 $A(x_i) \equiv y_i \pmod{10^9 + 9}$；
• 对于 $i = 0 \dots d$，满足 $a_i = a_{d-i}$。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 100$)。 测试用例描述如下。 每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 10^3$)，表示点的数量。 每个测试用例的第二行包含 $n$ 个不同的整数 $x_1, x_2, \dots, x_n$ ($0 \le x_i < 10^9 + 9$)。 每个测试用例的第三行包含 $n$ 个整数 $y_1, y_2, \dots, y_n$ ($0 \le y_i < 10^9 + 9$)。 保证所有测试用例的 $n$ 之和不超过 $10^3$。

输出格式

对于每个测试用例，如果不存在满足所有条件的多项式，则输出 $-1$。否则，在第一行输出找到的多项式的次数 $d$ ($0 \le d \le 10^4$)，并在下一行输出 $d+1$ 个整数 $a_0, a_1, \dots, a_d$ ($0 \le a_i < 10^9 + 9, a_d \neq 0$)。 如果存在多个解，输出其中任意一个即可。

样例

样例输入 1

8
2
0 1
2 4
3
0 1 2
2 10 36
4
0 1 2 3
1 4 9 16
5
0 1 2 3 4
1 25 961 14641 116281
2
2 500000005
5 375000004
2
2 500000005
5 375000004
2
2 500000005
1 2
3
2 500000005 3
5 375000004 10

样例输出 1

1
2 2
3
2 3 3 2
2
1 2 1
8
1 2 3 4 5 4 3 2 1
3
1 666666672 666666672 1
3
1 666666672 666666672 1
-1
-1

说明

次数为 $d$ 的多项式恰好有 $d+1$ 个系数，即使其中一些系数可能为零。除非多项式为常数零，否则多项式的首项系数不能为零。 因此，以下多项式是回文的：

• $A(x) = 2x^3 + 3x^2 + 3x + 2$ — 系数为 $[2, 3, 3, 2]$。
• $A(x) = 5x^4 + 10x^2 + 5$ — 系数为 $[5, 0, 10, 0, 5]$。
• $A(x) = x^4 + 1$ — 系数为 $[1, 0, 0, 0, 1]$。
• $A(x) = 1$ — 系数为 $[1]$。

以下多项式不是回文的：

• $A(x) = 2x^3 + 3x^2 + 3x + 1$ — 系数为 $[2, 3, 3, 1]$。
• $A(x) = 2x^4 + 3x^3 + 3x^2 + 2x$ — 系数为 $[2, 3, 3, 2, 0]$。
• $A(x) = x^5 + x$ — 系数为 $[1, 0, 0, 0, 1, 0]$。

作为特殊情况，多项式 $A(x) = 0$ 不满足条件 $a_d \neq 0$，因此不会被接受为答案。 另请注意，你不需要最小化多项式的次数。