你需要找到一个 $n$ 进制下的正整数 $A$，使得 $A$ 与自身拼接后构成的数是一个完全平方数，或者判定这样的数不存在。

输入格式

输入包含一行，为一个整数 $n$ ($2 \le n \le 10^7$)。

输出格式

如果这样的数 $A$ 不存在，或者其 $n$ 进制表示超过 3000 位，则仅输出两行 0。

否则，在第一行输出整数 $A$ 在 $n$ 进制下的位数，在第二行输出其各位数字。用 $0$ 到 $n-1$ 之间的十进制数表示每一位，相邻数字间用空格隔开。注意 $A$ 不能包含前导零。该数的 $n$ 进制位数不得超过 3000。

在第三行和第四行，以相同的格式输出 $\sqrt{AA}$ 在 $n$ 进制下的表示，其中 $AA$ 是将 $A$ 与自身拼接后得到的 $n$ 进制数。该数同样不能包含前导零。

样例

样例输入 1

2

样例输出 1

3
1 0 0
3
1 1 0

样例输入 2

3

样例输出 2

1
1
1
2

样例输入 3

32

样例输出 3

2
20 16
2
25 20

说明

第一个样例：$100100_2 = 36_{10} = 6^2$。