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