| Unknown Language Round 2 |
|---|
| Закончено |
- Io-2008-01-07 (Win32)
Гоштасп хорошо программирует, и все в его школе это знают. Однажды его друг Виштасп попросил решить задачу:
Дано натуральное число n, определите, является ли оно хорошим.
Натуральное число x называется хорошим, если существует набор различных чисел a1, a2, ..., am такой, что 
. При этом каждое число из набора ai либо должно быть простым, либо должно равняться единице.
Виштасп предлагает Гоштаспу разделить с ним свое Эйди поровну, если он сможет решить задачу. Эйди — это деньги, которые дарят детям на Новруз их родители и другие родственники.
Помогите Гоштаспу решить задачу!
В первой строке записано одно натуральное число n (1 ≤ n ≤ 10000).
Если число не является хорошим, выведите 0. Иначе выведите числа a1, ..., am. Если существует несколько решений, выведите лексикографически наибольшее из них. Решения сравниваются как последовательности чисел, а не как строки.
Чтобы сравнить последовательности a1, ..., am и b1, ..., bn найдите первый индекс i такой, что ai ≠ bi. Если ai < bi, то a лексикографически меньше, а если bi < ai, то b лексикографически меньше. Если m ≠ n, добавьте (только для сравнения) нули в конец меньшей последовательности и выполните сравнение.
Количество элементов в последовательности (m) минимизировать не требуется.
При выводе последовательности следуйте формату примеров.
11
11=11
545
541+3+1=545
