Cyclic Cipher
Contest: Codeforces Round 453 (Div. 1)
Difficulty rating: 3300
Tags: fft, math

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 $${ \{ b _ { i } \} } _ { i = 0 } ^ { n - 1 }$$, that acts as a key.

Vorpal is very selective, so the key should be such a sequence bi, that its cyclic shifts are linearly independent, that is, there is no non-zero set of coefficients x0, x1, ..., xn - 1, such that $$\sum_{i=0}^{n-1} x_i b_{k-i \bmod n} = 0$$ for all k at the same time.

After that for a sequence $$\{a_i\}_{i=0}^{n-1}$$ you should build the following cipher:

$$c_i = \sum_{k=0}^{n-1} (b_{k-i \mod n} - a_k)^2$$

In other words, you are to compute the quadratic deviation between each cyclic shift of bi and the sequence ai. 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 ci and bi. You are to find all suitable sequences ai.

Input format:
The first line contains a single integer n ($$1 \leq n \leq 10^5$$).

The second line contains n integers b0, b1, ..., bn - 1 ($$0 \leq b_i \leq 10^3$$).

The third line contains n integers c0, c1, ..., cn - 1 ($$0 \leq c_i \leq 5 \cdot 10^6$$).

It is guaranteed that all cyclic shifts of sequence bi are linearly independent.

Output format:
In the first line print a single integer k — the number of sequences ai, such that after encrypting them with key bi you get the sequence ci.

After that in each of k next lines print n integers a0, a1, ..., an - 1. Print the sequences in lexicographical order.

Note that k could be equal to 0.

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

Example input:
1
1
0

Example output:
1
1

Example input:
1
100
81

Example output:
2
91
109

Editorial:
(a - b)2 = a2 + b2 - 2ab, hence, $$c_k - c_{k-1} = -2 \sum_{i=0}^{n-1} b_i (a_{i+k} - a_{i+k-1})$$. Let a'i = ai - ai - 1, $$c_{k}^{\prime }=\frac{c_{k-1}-c_{k}}{2}$$. Then $$$$. This corresponds to cyclic convolution of polynomials $$B = \sum_{k=0}^{n-1} b_k x^k$$ and $$A = \sum_{k=0}^{n-1} a_k x^{n-k}$$. These polynomials uniquely determined by values in roots of unity of degree n. Thus we can divide values of C by values of B in this points and return to polynomials from values in roots of unity. To do this one should compute discrete Fourier Transform in arbitrary length polynomial which can be done by Bluestein's algorithm. Note that you can't use complex fft here because real values can be very close to zero leading to great precision issues. Thus you should find some mod having root of unity of degree 2n and compute discrete transform over it. Thus we will find dk = ak - a0 for each k, which will allow us to recover a0, because $$$$.
It can be proven that values of polynomial in roots of unity are eigenvalues of matrix of linear system thus cyclic shifts are linearly independent iff there is such mod which has root of unity of degree n and values of polynomial in all such roots doesn't equal zero. If it's true for polynomial in field of real numbers there will be only finite number of mods in which this may not be true (it only true if $${ \mathrm { g c d } }$$ of polynomial and xn - 1 isn't equal 1 in such mod).