<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

116. Index of super-prime

time limit per test: 0.25 sec.
memory limit per test: 4096 KB


Let P1, P2, … ,PN, … be a sequence of prime numbers. Super-prime number is such a prime number that its current number in prime numbers sequence is a prime number too. For example, 3 is a super-prime number, but 7 is not. Index of super-prime for number is 0 iff it is impossible to present it as a sum of few (maybe one) super-prime numbers, and if such presentation exists, index is equal to minimal number of items in such presentation. Your task is to find index of super-prime for given numbers and find optimal presentation as a sum of super-primes.


Input

There is a positive integer number in input. Number is not more than 10000.


Output

Write index I for given number as the first number in line. Write I super-primes numbers that are items in optimal presentation for given number. Write these I numbers in order of non-increasing.


Sample Input

6
Sample Output

2
3 3
Author	: Michael R. Mirzayanov
Resource	: PhTL #1 Training Contests
Date	: Fall 2001

<|response|>
1. Abridged problem statement  
Given a target integer n (1 ≤ n ≤ 10000), express n as a sum of one or more “super-prime” numbers using as few terms as possible.  
A super-prime is a prime whose index in the ordered list of all primes is itself prime.  
If no such sum exists, output 0. Otherwise, output:  
• First line: the minimal count I of terms in the sum.  
• Second line: I super-prime terms in non-increasing order that sum to n.

2. Key observations  
- We can precompute all primes up to n by the Sieve of Eratosthenes.  
- We can list them in order and mark as “super-prime” those primes whose 1-based position in the prime list is itself prime.  
- The task reduces to the classic unbounded coin-change problem where the “coins” are the super-primes ≤ n, and we seek the minimum number of coins summing to n.  
- A simple DP of size n+1 with dp[x] = minimum coins to make sum x suffices, since n ≤ 10000 and the number of super-primes is O(n/log n).  
- After filling dp[], if dp[n] is infinite (or −1) we print 0; otherwise we backtrack one valid choice at each step to recover an optimal list of coins, then sort them descending and print.

3. Full solution approach  
Step A: Sieve primes up to n  
  1. Create boolean array is_prime[0..n], initialize all true except 0 and 1.  
  2. For i from 2 to √n, if is_prime[i], mark multiples i*i, i*i+i, … ≤ n as non-prime.  
  3. As we discover each prime p, append it to a vector primes[].

Step B: Identify super-primes  
  1. Let m = primes.size(). Build a second sieve is_prime_idx[0..m] to test primality of indices.  
  2. For k from 1 to m, if is_prime_idx[k] is true, then primes[k−1] is a super-prime (because we use 1-based indexing).

Step C: Unbounded-knapsack DP  
  1. Let INF be a large sentinel (e.g. n+1). Create dp[0..n], fill all dp[i] = INF except dp[0] = 0.  
  2. For each super-prime s and for sum j from s to n:  
       dp[j] = min(dp[j], dp[j−s] + 1).  

Step D: Check feasibility  
  - If dp[n] is still INF, print 0 and exit.  

Step E: Reconstruct one optimal solution  
  1. Let cur = n, ans = empty list.  
  2. While cur > 0:  
       • Iterate over the super-prime list, and find an s ≤ cur such that dp[cur−s] == dp[cur]−1.  
       • Append s to ans, set cur -= s, break the scan.  
  3. At the end, ans contains dp[n] terms, possibly unordered.

Step F: Output  
  1. Print dp[n] on its own line.  
  2. Sort ans in non-increasing order, then print its elements on the next line separated by spaces.

Time complexity:  
- Sieve: O(n log log n).  
- DP: O(n × #super_primes) ≤ O(10000 × ~1200) in practice.  
- Reconstruction: O(dp[n] × #super_primes).  
All steps run well under the time/memory limits.

4. C++ implementation with detailed comments  
```cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    if (n < 2) {
        // No super-prime ≥ 2 can form sum < 2
        cout << 0 << "\n";
        return 0;
    }

    // Step A: Sieve primes up to n
    vector<bool> is_prime(n+1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i*i <= n; ++i) {
        if (!is_prime[i]) continue;
        for (int j = i*i; j <= n; j += i)
            is_prime[j] = false;
    }
    // Collect all primes in order
    vector<int> primes;
    for (int i = 2; i <= n; ++i) {
        if (is_prime[i])
            primes.push_back(i);
    }

    // Step B: Identify super-primes
    int m = primes.size();
    // Sieve up to m to test which indices are prime
    vector<bool> is_prime_idx(m+1, true);
    is_prime_idx[0] = is_prime_idx[1] = false;
    for (int i = 2; i*i <= m; ++i) {
        if (!is_prime_idx[i]) continue;
        for (int j = i*i; j <= m; j += i)
            is_prime_idx[j] = false;
    }
    // Build list of super-primes
    vector<int> super_primes;
    for (int k = 1; k <= m; ++k) {
        if (is_prime_idx[k]) {
            // primes is zero-indexed, k is 1-based
            super_primes.push_back(primes[k-1]);
        }
    }

    // Step C: DP for unbounded coin change
    const int INF = n + 1;
    vector<int> dp(n+1, INF);
    dp[0] = 0;
    for (int s : super_primes) {
        for (int sum = s; sum <= n; ++sum) {
            if (dp[sum - s] + 1 < dp[sum]) {
                dp[sum] = dp[sum - s] + 1;
            }
        }
    }

    // Step D: Check feasibility
    if (dp[n] >= INF) {
        cout << 0 << "\n";
        return 0;
    }

    // Step E: Reconstruct one solution
    int cur = n;
    vector<int> answer;
    while (cur > 0) {
        // find a super-prime s that was used
        for (int s : super_primes) {
            if (s <= cur && dp[cur - s] == dp[cur] - 1) {
                answer.push_back(s);
                cur -= s;
                break;
            }
        }
    }

    // Step F: Output
    cout << answer.size() << "\n";
    sort(answer.rbegin(), answer.rend());
    for (int x : answer) {
        cout << x << " ";
    }
    cout << "\n";
    return 0;
}
```

5. Python implementation with detailed comments  
```python
import sys

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    n = int(data[0])
    if n < 2:
        # Cannot form any sum of super-primes
        print(0)
        return

    # Step A: Sieve primes up to n
    is_prime = [True] * (n+1)
    is_prime[0] = is_prime[1] = False
    p = 2
    while p*p <= n:
        if is_prime[p]:
            for j in range(p*p, n+1, p):
                is_prime[j] = False
        p += 1
    primes = [i for i in range(2, n+1) if is_prime[i]]

    # Step B: Identify super-primes
    m = len(primes)
    is_prime_idx = [True] * (m+1)
    is_prime_idx[0] = is_prime_idx[1] = False
    i = 2
    while i*i <= m:
        if is_prime_idx[i]:
            for j in range(i*i, m+1, i):
                is_prime_idx[j] = False
        i += 1
    super_primes = [primes[k-1] for k in range(1, m+1) if is_prime_idx[k]]

    # Step C: DP for minimum coins
    INF = n + 1
    dp = [INF] * (n+1)
    dp[0] = 0
    for coin in super_primes:
        for s in range(coin, n+1):
            if dp[s-coin] + 1 < dp[s]:
                dp[s] = dp[s-coin] + 1

    # Step D: Feasibility
    if dp[n] >= INF:
        print(0)
        return

    # Step E: Reconstruct one optimal solution
    ans = []
    cur = n
    while cur > 0:
        for coin in super_primes:
            if coin <= cur and dp[cur-coin] == dp[cur] - 1:
                ans.append(coin)
                cur -= coin
                break

    # Step F: Output
    print(len(ans))
    ans.sort(reverse=True)
    print(*ans)

if __name__ == "__main__":
    main()
```