Codeforces Round 453 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

fft

math

*3300

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Cyclic Cipher

time limit per test

5 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputSenor 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.

Examples

Input

1

1

0

Output

1

1

Input

1

100

81

Output

2

91

109

Input

3

1 1 3

165 185 197

Output

2

-6 -9 -1

8 5 13

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/28/2024 06:43:04 (k3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|