← 返回题目列表

Codeforces · 901/E

E. 循环密码

中文机器翻译题面 查看原题

Senor Vorpal Kickass'o 发明了一种创新方法来加密长度为 n 的整数序列。要加密序列,必须选择一个秘密序列 $${ \{ b _ { i } \} } _ { i = 0 } ^ { n - 1 }$$ 作为密钥。

Vorpal 具有很强的选择性,因此密钥应该是这样一个序列 bi,其循环移位是线性无关的,即不存在非零系数集 x0, x1, ..., xn - 1,使得 $$\sum_{i=0}^{n-1} x_i b_{k-i \bmod n} = 0$$ 同时对于所有 k。

之后,对于序列 $$\{a_i\}_{i=0}^{n-1}$$ 您应该构建以下密码:

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

换句话说,您要计算 bi 和序列 ai 的每次循环移位之间的二次偏差。得到的序列就是 Kickass 的密码。该密码目前正在开发中,Vorpal 想要破译加密后的序列。你要为他解决这个问题。给定序列 ci 和 bi。你要找到所有合适的序列ai。

输入

第一行包含一个整数 n ($$1 \leq n \leq 10^5$$)。

第二行包含 n 个整数 b0, b1, ..., bn - 1 ($$0 \leq b_i \leq 10^3$$)。

第三行包含 n 个整数 c0, c1, ..., cn - 1 ($$0 \leq c_i \leq 5 \cdot 10^6$$)。

保证序列bi的所有循环移位都是线性无关的。

输出

在第一行中打印一个整数 k - 序列 ai 的数量,这样在使用密钥 bi 加密它们之后,你就得到了序列 ci。

之后,在接下来的 k 行中的每一行中打印 n 个整数 a0, a1, ..., an - 1。按字典顺序打印序列。

请注意,k 可以等于 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