F. Palindromic Polynomial
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Author: Dmytro Fedoriaka

A palindromic polynomial is a non-zero polynomial whose coefficients read the same in both directions.

Alan had a palindromic polynomial $$$A$$$ of a degree $$$d \le 10^4$$$. He wrote down its values modulo $$$10^9+9$$$ in $$$n$$$ distinct integer points. Then he lost the polynomial. Now he wants to restore it from the points. Help Alan find any palindromic polynomial of degree at most $$$10^4$$$ which passes through all given points.

Formally, you are given a list of pairs $$$(x_1, y_1), (x_2, y_2) \dots (x_n, y_n)$$$, $$$0 \le x_i, y_i \lt 10^9+9$$$. Your task is to find any polynomial $$$A(x) = a_d x^d + a_{d-1} x^{d-1} + \dots + a_1 x + a_0$$$, such that:

  • $$$0 \le d \le 10^4$$$ and $$$a_d \neq 0$$$;
  • $$$0 \le a_i \lt 10^9+9$$$ for $$$i=0 \dots d$$$;
  • $$$A(x_i) \equiv y_i ~(\text{mod}~ 10^9+9)$$$ for $$$i=1\dots n$$$;
  • $$$a_i = a_{d-i}$$$ for $$$i=0\dots d$$$.
Input

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

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 10^3$$$) — the number of points.

The second line of each test case contains $$$n$$$ distinct integers $$$x_1, x_2, \dots, x_n$$$ ($$$0 \le x_i \lt 10^9+9$$$).

The third line of each test case contains $$$n$$$ integers $$$y_1, y_2, \dots y_n$$$ ($$$0 \le y_i \lt 10^9+9$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^3$$$.

Output

For each test case, print $$$-1$$$ if there is no polynomial that satisfies all the conditions. Otherwise, on the first line print $$$d$$$ — the degree of the found polynomial ($$$0 \le d \le 10^4$$$), and on the next line print $$$d+1$$$ integers $$$a_0, a_1, \dots, a_d$$$ ($$$0 \le a_i \lt 10^9+9$$$, $$$a_d \ne 0$$$).

If there are multiple solutions, print any of them.

Example
Input
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
Output
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
Note

The polynomial of degree $$$d$$$ has exactly $$$d+1$$$ coefficients, even though some of them may be zeros. The leading coefficient of a polynomial cannot be zero unless the polynomial is constant zero.

Hence, the following polynomials are palindromic:

  • $$$A(x) = 2 x^3 + 3 x^2 + 3 x + 2$$$ — coefficients are $$$[2, 3, 3, 2]$$$.
  • $$$A(x) = 5 x^4 + 10 x^2 + 5$$$ — coefficients are $$$[5, 0, 10, 0, 5]$$$.
  • $$$A(x) = x^4 + 1$$$ — coefficients are $$$[1, 0, 0, 0, 1]$$$.
  • $$$A(x) = 1$$$ — coefficients are $$$[1]$$$.

The following polynomials are not palindromic:

  • $$$A(x) =2 x^3 + 3 x^2 + 3 x + 1$$$ — coefficients are $$$[2, 3, 3, 1]$$$.
  • $$$A(x) =2 x^4 + 3 x^3 + 3 x^2 + 2x$$$ — coefficients are $$$[2, 3, 3, 2, 0]$$$.
  • $$$A(x) = x^5 + x$$$ — coefficients are $$$[1, 0, 0, 0, 1, 0]$$$.

As a special case, the polynomial $$$A(x)=0$$$ does not satisfy condition $$$a_d \ne 0$$$ and will not be accepted as an an answer.

Also note that you do not need to minimize the degree of the polynomial.