← 返回题目列表

Codeforces · 584/D

D. 迪玛和丽莎

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

Dima 喜欢将奇数表示为多个素数之和,而 Lisa 喜欢最多有 3 个素数。帮助他们将给定的数字表示为最多三个以上素数的和。

更正式地说,您得到一个奇数 n。找到一组数字 pi (1 ≤ i ≤ k),使得

1. 1 ≤ k ≤ 3
2. pi 是素数
3. $$\sum_{i=1}^{k} p_i = n$$

数字 pi 不一定必须不同。保证至少存在一种可能的解决方案。

输入

单行包含奇数 n (3 ≤ n < 109)。

输出

在第一行中打印 k (1 ≤ k ≤ 3),显示您找到的表示中有多少个数字。

在第二行以任意顺序打印数字 pi。如果有多种可能的解决方案,您可以打印其中任何一个。

示例

输入 #1

27

输出 #1

3
5 11 11

注意

素数是严格大于 1 且只能被 1 和自身整除的整数。