Cyclic Cipher

题意翻译

## 题目描述 Senor Vorpal Kickass'o 发明了一种加密长度为 $n$ 的整数序列的方法. 首先其会选择一个作为密钥的序列 $b$, $b$ 循环线性无关,即 $$\nexists x_0, x_1,...,x_{n-1},s.t.\forall k,\sum_{i=0}^{n-1}x_ib_{k-i\mod n}=0$$ 对于一个序列 $a$ 可以通过如下方式得到一个序列 $c$： $$c_i=\sum_{k=0}^{n-1}(b_{k-i\mod n}-a_k)^2$$ 现在给定序列 $b$ 和序列 $c$，要求输出所有满足条件件的序列 $a$。

题目描述

Senor Vorpal Kickass'o invented an innovative method to encrypt integer sequences of length $ n $ . To encrypt a sequence, one has to choose a secret sequence , that acts as a key. Vorpal is very selective, so the key should be such a sequence $ b_{i} $ , that its cyclic shifts are linearly independent, that is, there is no non-zero set of coefficients $ x_{0},x_{1},...,x_{n-1} $ , such that  for all $ k $ at the same time. After that for a sequence  you should build the following cipher: In other words, you are to compute the quadratic deviation between each cyclic shift of $ b_{i} $ and the sequence $ a_{i} $ . The resulting sequence is the Kickass's cipher. The cipher is in development right now and Vorpal wants to decipher a sequence after it has been encrypted. You are to solve this problem for him. You are given sequences $ c_{i} $ and $ b_{i} $ . You are to find all suitable sequences $ a_{i} $ .

输入输出格式

输入格式

The first line contains a single integer $ n $ (). The second line contains $ n $ integers $ b_{0},b_{1},...,b_{n-1} $ (). The third line contains $ n $ integers $ c_{0},c_{1},...,c_{n-1} $ (). It is guaranteed that all cyclic shifts of sequence $ b_{i} $ are linearly independent.

输出格式

In the first line print a single integer $ k $ — the number of sequences $ a_{i} $ , such that after encrypting them with key $ b_{i} $ you get the sequence $ c_{i} $ . After that in each of $ k $ next lines print $ n $ integers $ a_{0},a_{1},...,a_{n-1} $ . Print the sequences in lexicographical order. Note that $ k $ could be equal to $ 0 $ .

输入输出样例

输入样例 #1

1
1
0

输出样例 #1

1
1

输入样例 #2

1
100
81

输出样例 #2

2
91
109

输入样例 #3

3
1 1 3
165 185 197

输出样例 #3

2
-6 -9 -1
8 5 13