Codeforces 749A (Bachgold Problem)

Codeforces 749A (Bachgold Problem)

time limit per test-

1 second

memory limit per test-

256 megabytes

input-

standard input

output-

standard output

Bachgold problem is very easy to formulate. Given a positive integer n represent it as a sum of maximum possible number of prime numbers. One can prove that such representation exists for any integer greater than 1.

Recall that integer k is called prime if it is greater than 1 and has exactly two positive integer divisors — 1 and k.

Input

The only line of the input contains a single integer n (2 ≤ n ≤ 100 000).

Output

The first line of the output contains a single integer k — maximum possible number of primes in representation.

The second line should contain k primes with their sum equal to n. You can print them in any order. If there are several optimal solution, print any of them.

Examples

input

5

output

2
2 3

input

6

output

3
2 2 2

Solution:

#include<bits/stdc++.h>

using namespace std;

vector<long long int> a;

int  main()

{

    long long int y,c,d;

    scanf("%lld",&y);

    for( c=1; c<sqrt(y); c++)

    {

        if(y%c==0)

        {

            a.push_back(c);

            a.push_back(y/c);

        }

    }

    if(c*c==y)

    {

        a.push_back(c);

    }

    sort(a.begin(),a.end());

    long long int h;

    scanf("%lld",&h);

    if(h<=a.size())

        printf("%lld\n",a[h-1]);

    else

        printf("-1\n");

    return 0;

}