<|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 with the Sieve of Eratosthenes.
- We can list them in order and mark as “super-prime” those primes whose 1-based position cnt in the prime list is itself prime. Since cnt ≤ the prime value itself, we can test primality of cnt with the very same sieve.
- 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.
- After filling dp[], if dp[n] is unreachable (−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: Generate super-primes
  1. Sieve primes up to a safe bound (the reference uses 10^6).
  2. Walk i from 2 upward; keep a counter cnt of primes seen. When i is prime, increment cnt; if cnt is also prime (same sieve), then i is a super-prime.

Step B: Unbounded-knapsack DP
  1. Create dp[0..n], fill all dp[i] = −1 except dp[0] = 0.
  2. For each super-prime s and for sum j from s to n: if dp[j−s] is reachable, set dp[j] = min(dp[j], dp[j−s] + 1).

Step C: Check feasibility
  - If dp[n] is still −1, print 0 and exit.

Step D: Reconstruct one optimal solution
  1. Let cur = n, ans = empty list.
  2. While cur > 0: find a super-prime s ≤ cur with dp[cur−s] == dp[cur]−1; append s, set cur −= s, break the scan.

Step E: Output
  1. Print dp[n] (= ans.size()) on its own line.
  2. Sort ans in non-increasing order, then print its elements.

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

4. C++ implementation
```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

vector<int> super_primes(int n) {
    vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false;

    int cnt = 0;
    vector<int> res;
    for(int i = 2; i <= n; i++) {
        if(is_prime[i]) {
            cnt++;
            if(is_prime[cnt]) {
                res.push_back(i);
            }

            for(int64_t j = i * 1ll * i; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }

    return res;
}

vector<int> sp;
int n;

void read() { cin >> n; }

void solve() {
    // A super-prime is the k-th prime where k itself is prime. We precompute
    // all super-primes by sieving and checking that the prime's index is
    // prime. Then this is an unbounded coin-change: dp[j] = fewest super-primes
    // summing to j (-1 if impossible). We reconstruct one optimal multiset by
    // greedily peeling off a super-prime that keeps dp on an optimal path, and
    // print the summands in non-increasing order.

    vector<int> dp(n + 1, -1);
    dp[0] = 0;
    for(int i = 0; i < (int)sp.size(); i++) {
        for(int j = sp[i]; j <= n; j++) {
            if(dp[j - sp[i]] != -1) {
                if(dp[j] == -1 || dp[j - sp[i]] + 1 < dp[j]) {
                    dp[j] = dp[j - sp[i]] + 1;
                }
            }
        }
    }

    if(dp[n] == -1) {
        cout << 0 << '\n';
        return;
    }

    vector<int> ans;
    while(n > 0) {
        for(int i = 0; i < (int)sp.size(); i++) {
            if(n >= sp[i] && dp[n - sp[i]] == dp[n] - 1) {
                ans.push_back(sp[i]);
                n -= sp[i];
                break;
            }
        }
    }

    cout << ans.size() << '\n';
    sort(ans.rbegin(), ans.rend());
    cout << ans << '\n';
}

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

    sp = super_primes((int)1e6);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    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)
    if 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()
```
