{"raw_statement":[{"iden":"statement","content":"<center>![image](https://espresso.codeforces.com/91b468d78347fe8904bdab04bd29243f20376a13.png)</center>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.\n\nVorpal 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.\n\nAfter that for a sequence you should build the following cipher:\n\nIn 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_."},{"iden":"input","content":"The first line contains a single integer _n_ ().\n\nThe second line contains _n_ integers _b_0, _b_1, ..., _b__n_ - 1 ().\n\nThe third line contains _n_ integers _c_0, _c_1, ..., _c__n_ - 1 ().\n\nIt is guaranteed that all cyclic shifts of sequence _b__i_ are linearly independent."},{"iden":"output","content":"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_.\n\nAfter that in each of _k_ next lines print _n_ integers _a_0, _a_1, ..., _a__n_ - 1. Print the sequences in lexicographical order.\n\nNote that _k_ could be equal to 0."},{"iden":"examples","content":"Input\n\n1\n1\n0\n\nOutput\n\n1\n1\n\nInput\n\n1\n100\n81\n\nOutput\n\n2\n91\n109\n\nInput\n\n3\n1 1 3\n165 185 197\n\nOutput\n\n2\n-6 -9 -1\n8 5 13"}],"translated_statement":[{"iden":"statement","content":"Senor Vorpal Kickass'o 发明了一种创新的方法来加密长度为 $n$ 的整数序列。要加密一个序列，需要选择一个作为密钥的保密序列 $b_i$。\n\nVorpal 非常挑剔，因此密钥应是一个序列 $b_i$，其所有循环移位是线性无关的，即不存在一组非全零的系数 $x_0, x_1, ..., x_{n - 1}$，使得对所有 $k$ 同时成立 $\\sum_{i=0}^{n-1} x_i \\cdot b_{(i+k) \\bmod n} = 0$。\n\n之后，对于序列 $a_i$，你需要构建如下加密结果：\n\n换句话说，你需要计算每个 $b_i$ 的循环移位与序列 $a_i$ 之间的二次偏差。得到的序列即为 Kickass 的加密结果。该加密方法尚在开发中，Vorpal 希望在加密后能够解密序列。你需要帮他解决这个问题。你将获得序列 $c_i$ 和 $b_i$，你需要找出所有符合条件的序列 $a_i$。\n\n第一行包含一个整数 $n$（$1 \\le n \\le 2000$）。\n\n第二行包含 $n$ 个整数 $b_0, b_1, ..., b_{n - 1}$（$-10^9 \\le b_i \\le 10^9$）。\n\n第三行包含 $n$ 个整数 $c_0, c_1, ..., c_{n - 1}$（$0 \\le c_i \\le 10^{18}$）。\n\n保证序列 $b_i$ 的所有循环移位线性无关。\n\n第一行输出一个整数 $k$ —— 满足使用密钥 $b_i$ 加密后得到序列 $c_i$ 的序列 $a_i$ 的数量。\n\n随后在接下来的 $k$ 行中，每行输出 $n$ 个整数 $a_0, a_1, ..., a_{n - 1}$。请按字典序输出这些序列。\n\n注意 $k$ 可能为 0。"},{"iden":"input","content":"第一行包含一个整数 $n$（$1 \\le n \\le 2000$）。第二行包含 $n$ 个整数 $b_0, b_1, ..., b_{n - 1}$（$-10^9 \\le b_i \\le 10^9$）。第三行包含 $n$ 个整数 $c_0, c_1, ..., c_{n - 1}$（$0 \\le c_i \\le 10^{18}$）。保证序列 $b_i$ 的所有循环移位线性无关。"},{"iden":"output","content":"第一行输出一个整数 $k$ —— 满足使用密钥 $b_i$ 加密后得到序列 $c_i$ 的序列 $a_i$ 的数量。随后在接下来的 $k$ 行中，每行输出 $n$ 个整数 $a_0, a_1, ..., a_{n - 1}$。请按字典序输出这些序列。注意 $k$ 可能为 0。"},{"iden":"examples","content":"输入110输出11输入110081输出291109输入31 1 3165 185 197输出2-6 -9 -18 5 13"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $.  \nLet $ \\mathbf{b} = (b_0, b_1, \\dots, b_{n-1}) \\in \\mathbb{R}^n $ be the secret key sequence, such that its $ n $ cyclic shifts are linearly independent over $ \\mathbb{R} $.  \nLet $ \\mathbf{c} = (c_0, c_1, \\dots, c_{n-1}) \\in \\mathbb{R}^n $ be the given encrypted sequence.  \nLet $ \\mathbf{a} = (a_0, a_1, \\dots, a_{n-1}) \\in \\mathbb{R}^n $ be the unknown plaintext sequence.  \n\nFor $ j \\in \\{0, 1, \\dots, n-1\\} $, define the $ j $-th cyclic shift of $ \\mathbf{b} $ as:  \n$$\n\\mathbf{b}^{(j)} = (b_j, b_{j+1}, \\dots, b_{n-1}, b_0, \\dots, b_{j-1})\n$$\n\nThe encryption is defined by:  \n$$\nc_j = \\sum_{i=0}^{n-1} (a_i - b_{(i+j) \\bmod n})^2, \\quad \\forall j \\in \\{0, 1, \\dots, n-1\\}\n$$\n\n**Constraints**  \n1. $ 1 \\le n \\le 2000 $  \n2. $ |b_i| \\le 10^6 $, $ |c_j| \\le 10^{12} $  \n3. The set $ \\{ \\mathbf{b}^{(0)}, \\mathbf{b}^{(1)}, \\dots, \\mathbf{b}^{(n-1)} \\} $ is linearly independent over $ \\mathbb{R} $.\n\n**Objective**  \nFind all $ \\mathbf{a} \\in \\mathbb{R}^n $ such that:  \n$$\nc_j = \\|\\mathbf{a} - \\mathbf{b}^{(j)}\\|_2^2, \\quad \\forall j \\in \\{0, 1, \\dots, n-1\\}\n$$  \nOutput the number $ k $ of such sequences $ \\mathbf{a} $, followed by all $ \\mathbf{a} $ in lexicographical order.","simple_statement":null,"has_page_source":false}