密码

题目描述

小 Y 想要加密一个长度为 $n$ 的整数数列 $a$。

他找了一个长度为 $n$ 的自然数数列 $b$ ，满足

$$\det\left(\begin{bmatrix}b_0&t_1&b_2&b_3&\dots&b_{n-1}\\b_1&b_2&b_3&b_4&\dots&b_{0}\\b_2&b_3&b_4&b_5&\dots&b_{1}\\\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\b_{n-1}&b_0&b_1&b_2&\dots&b_{n-2}\end{bmatrix}\right)\neq0 $$

即 $t$ 构成的循环矩阵线性无关。

他通过一些操作计算出了数列 $c_i=\sum\limits_{k=0}^{n-1}(b_{(k-i)\bmod n}-a_k)^2$。

一段时间后，小 H 想要破译 $a$ 的值，但不幸的是它只知道 $b$ 和 $c$。它需要求出所有可能的 $a$。如果可能的 $a$ 太多，那它就只需要知道可能的 $a$ 的个数即可。

输入格式

第一行一个数 $n$。

第二行 $n$ 个自然数，表示 $b_i$。

第三行 $n$ 个自然数，表示 $c_i$。

输出格式

第一行一个数 $k$，表示答案组数。

如果答案组数 $\le 10$，则在接下来的 $k$ 行内，输出一个长为 $n$ 的整数数列表示所有可能的答案，按照字典序升序排列。

样例

Input #1:

4
1 2 3 4
4 3 2 1

Output #1:

0

Input #2:

3
1 2 3
0 6 6

Output #2:

1
1 2 3

Input #3:

1
10
64

Output #3:

2
2
18

数据范围

$1\le n\le 10^5,0\le b_i\le 10^3,0\le c_i\le 5\times 10^6$。

Subtask1：$n,b_i\le 5,c_i \le 50$。（17pts）

Subtask2：$n\le 50,b_i\le 100,c_i\le 5\times 10^4$。（10 pts）

Subtask3：$n\le 100$。（15 pts）

Subtask4：$n$ 为 $2$ 的幂次（21 pts）

Subtask5：$n\le 1000$。（23 pts）

Subtask6：无特殊限制。（14 pts）