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*}$.

Input

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.

Output

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$.