← 返回题目列表

Codeforces · 72/A

A. Goshtasp、Vishtasp 和 Eidi

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

Goshtasp 在他的学校是一名优秀的程序员。有一天,Goshtasp 的朋友 Vishtasp 让他解决这个任务:

给定一个正整数n,你应该判断n是否丰富。

正整数 x 是丰富的,如果存在一组不同的数字 a1, a2, ..., am 使得 $$\sum_{i=1}^{m}a_{i}=x$$。另外:每个ai 要么是素数,要么等于1。

Vishtasp 说,如果他能解决这个任务,他会与 Goshtasp 分享他的 Eidi 50 / 50。 Eidi 是父母和/或亲戚为 Noruz 孩子们提供的钱。

Goshtasp需要解决这个问题才能获得金钱,你需要解决它才能获得分数!

输入

输入包含单个正整数 n (1 ≤ n ≤ 10000)。

输出

如果数字不丰富则打印 0。否则打印数字 a1, ..., am。如果存在多个解决方案,则打印按字典顺序排列的最新解决方案。答案作为数字序列而不是字符串进行比较。

为了比较两个序列 a1, ..., am 和 b1, ..., bn,我们首先找到第一个索引 i,使得 ai ≠ bi,如果 ai < bi,则 a 在字典顺序上更早,如果 bi < ai,则 b 在字典顺序上更早。如果 m ≠ n,我们在较小序列的末尾添加零(仅用于比较时刻),然后执行比较。

您不需要最小化序列中元素的数量(即 m)。您只需打印按字典顺序排列的最新解决方案即可。

请参阅示例以了解如何打印序列。

示例

输入 #1

11

输出 #1

11=11

输入 #2

545

输出 #2

541+3+1=545