$\text{[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 $\text{[math]}$ , 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₀, x₁, ..., x_n - 1, such that $\text{[math]}$ for all k at the same time.

After that for a sequence $\text{[math]}$ you should build the following cipher:

$\text{[math]}$

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 ( $\text{[math]}$ ).

The second line contains n integers b₀, b₁, ..., b_n - 1 ( $\text{[math]}$ ).

The third line contains n integers c₀, c₁, ..., c_n - 1 ( $\text{[math]}$ ).

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₀, a₁, ..., a_n - 1. Print the sequences in lexicographical order.

Note that k could be equal to 0.

Cyclic Cipher

Examples