Dima loves representing an odd number as the sum of multiple primes, and Lisa loves it when there are at most three primes. Help them to represent the given number as the sum of at most than three primes.

More formally, you are given an odd numer n. Find a set of numbers p_{i} (1 ≤ i ≤ k), such that



 1 ≤ k ≤ 3

 p_{i} is a prime

 $\sum_{i = 1}^{k} p_{i} = n$

The numbers p_{i} do not necessarily have to be distinct. It is guaranteed that at least one possible solution exists.


-----Input-----

The single line contains an odd number n (3 ≤ n < 10^9).


-----Output-----

In the first line print k (1 ≤ k ≤ 3), showing how many numbers are in the representation you found.

In the second line print numbers p_{i} in any order. If there are multiple possible solutions, you can print any of them.


-----Examples-----
Input
27

Output
3
5 11 11



-----Note-----

A prime is an integer strictly larger than one that is divisible only by one and by itself.

Difficulty: interview

Starter code:

Solutions:
import math

n=int(input())

def prime(p):
    if p == 1:
        return False
    fl=True
    for i in range(2,math.ceil(p**0.5) + 1):
        if p % i == 0:
            fl=False
    return fl

def sum_of_primes(k):
    fl=True
    for i in range((k // 2) + 1):
        if prime(i) and prime(k-i):
            fl=True
            break
    return fl

if prime(n):
    print(1)
    print(n)
else:
    if prime(n-2):
        print(2)
        print(2 , n-2)
    else:
        l=1
        for i in range(2, (n // 3) + 1):
            if prime(i) and sum_of_primes(n - i):
                l=i
                break
        print(3)
        r=1
        for k in range((n-l) // 2):
            if prime(k) and prime(n-l-k):
                r=k
                break
        print(l,r,n-l-r)

            


from sys import *
def prime(a):
   if a<2: return False
   for j in range(2,int(a**0.5)+1):
      if a%j==0: return False
   return True
p=[i for i in range(2,10000) if prime(i)]
lp=len(p)    

n=int(input())
if prime(n):
   print("1\n",n)
   return
if n>3 and prime(n-2):
         print("2\n",2,n-2)
         return
if n>5 and prime(n-4):
         print("3\n",2,2,n-4)
         return

for j in range(lp):
   for i in range(j,lp):
      if p[j]+p[i]+2>n: break
      if prime(n-p[i]-p[j]):
          print("3\n",p[j],p[i],n-p[i]-p[j])
          return


def primes2(limit):
    if limit < 2: return []
    if limit < 3: return [2]
    lmtbf = (limit - 3) // 2
    buf = [True] * (lmtbf + 1)
    for i in range((int(limit ** 0.5) - 3) // 2 + 1):
        if buf[i]:
            p = i + i + 3
            s = p * (i + 1) + i
            buf[s::p] = [False] * ((lmtbf - s) // p + 1)
    return [2] + [i + i + 3 for i, v in enumerate(buf) if v]

n = int(input())
ps = primes2(int(n**0.5) + 1)

def solve(n):
    if is_prime(n):
        return [n]
    for m in range(n - 2, n//3 - 1, -1):
        if is_prime(m):
            r = n - m
            if is_prime(r):
                return [m, r]
            for s in range(r - 2, r//2 - 1, -1):
                if is_prime(s) and is_prime(r - s):
                    return [m, s, r - s]

def is_prime(n):
    sqrt_n = int(n ** 0.5)
    for p in ps:
        if n == p:
            return True
        if n % p == 0:
            return False
        if p > sqrt_n:
            return True
    return True


ans = solve(n)
print(len(ans))
print(*ans)

def prime(i):
    for k in range(2, int(i**0.5)+1):
        if i%k == 0:
            return False
    return True

x = int(input())
if prime(x):
    print(1)
    print(x)
    quit()
i = x
while not prime(i):
    i -= 2

p1000 = [i for i in range(2, 3000) if prime(i)]

rem = x - i
if rem == 2:
    print(2)
    print(2, i)
    quit()

print(3)
for jj in p1000:
    if rem-jj in p1000:
        print(i, jj, rem-jj)
        quit()


import math
def is_prime(a):
    n=math.sqrt(a)
    n=int(n)+1
    return all(a % i for i in range(2, n))
def sieves(n):
    size = n//2
    sieve = [1]*size
    limit = int(n**0.5)
    for i in range(1,limit):
        if sieve[i]:
            val = 2*i+1
            tmp = ((size-1) - i)//val 
            sieve[i+val::val] = [0]*tmp
    return [2] + [i*2+1 for i, v in enumerate(sieve) if v and i>0]
pri=sieves(1000)
n=int(input())
for i in range(n,1,-1):
    if is_prime(i):
        primes=i
        break

ans=[]
no=1
if n==primes:
    ans=[n]
    no=1

elif primes+2==n:
    ans=[2,primes]
    no=2
else:
    k=n-primes
    for i in pri:
        for j in pri:
            if i+j==k:
                ans=[primes,i,j]
                no=3
print(no)
for i in ans:
    print(i,end=' ')

import math
def Prost(n):
    for i in range(2,int(math.sqrt(n))+1):
        if n%i==0:
            return False
    else:
        return True
n = int(input())
r=0
if Prost(n):
    print(1)
    print(n)
else:
    for i in range(n-1,n-300,-1):
        if Prost(i):
            r=i
            break
    
    k=n-r
    if (k==2):
        print(2)
        print(r,k) 
    else:
        for i in range(2,k):
            if Prost(i) and Prost(k-i):
                print(3)
                print(r,i,k-i)
                break


def miller_rabin(n):
    """ primality Test
        if n < 3,825,123,056,546,413,051, it is enough to test
        a = 2, 3, 5, 7, 11, 13, 17, 19, and 23.
        Complexity: O(log^3 n)
    """
    if n == 2:
        return True
    if n <= 1 or not n & 1:
        return False

    primes = [2, 3, 5, 7, 11, 13, 17, 19, 23]

    d = n - 1
    s = 0
    while not d & 1:
        d >>= 1
        s += 1

    for prime in primes:
        if prime >= n:
            continue
        x = pow(prime, d, n)
        if x == 1:
            continue
        for r in range(s):
            if x == n - 1:
                break
            if r + 1 == s:
                return False
            x = x * x % n
    return True

N = int(input())

if miller_rabin(N):
    print(1)
    print(N)
elif miller_rabin(N-2):
    print(2)
    print(2, N-2)
elif miller_rabin(N-4):
    print(3)
    print(2, 2, N-4)
else:
    i = 3
    while True:
        if miller_rabin(i):
            if miller_rabin((N-i)//2):
                print(3)
                print(i, (N-i)//2, (N-i)//2)
                break
            elif miller_rabin(N-2*i):
                print(3)
                print(i, i, N-2*i)
                break
        i += 2


import math

def is_prime(x):
    for i in range(2, int(math.sqrt(x)) + 1):
        if x % i == 0:
            return False
    return True
def decomposition(even):
    if even == 4: return 2, 2
    for i in range(even - 3, int(math.sqrt(even)) - 1, -2):
        if is_prime(i) and is_prime(even - i):
            return i, even - i

n = int(input())
if is_prime(n): 
    print(1)
    print(n)
else:
    for i in range(n, 3, -2):
        if is_prime(i):
            if n - i == 2:
                print(2)
                print(i, 2)
                break
            else:
                print(3)
                print(i, *decomposition(n - i))
                break


import math
def is_prime(a):
    n=math.sqrt(a)
    n=int(n)+1
    return all(a % i for i in range(2, n))
def sieves(n):
    size = n//2
    sieve = [1]*size
    limit = int(n**0.5)
    for i in range(1,limit):
        if sieve[i]:
            val = 2*i+1
            tmp = ((size-1) - i)//val 
            sieve[i+val::val] = [0]*tmp
    return [2] + [i*2+1 for i, v in enumerate(sieve) if v and i>0]
pri=sieves(400)
n=int(input())
for i in range(n,1,-2):
    if is_prime(i):
        primes=i
        break

ans=[]
no=1
if n==primes:
    ans=[n]
    no=1

elif primes+2==n:
    ans=[2,primes]
    no=2
else:
    k=n-primes
    for i in pri:
        for j in pri:
            if i+j==k:
                ans=[primes,i,j]
                no=3
print(no)
for i in ans:
    print(i,end=' ')

def isPrime(n):
    if n==2:
        return True
    if n%2==0:
        return False
    for i in range(3,n,2):
        if i*i>n:
            break
        if n%i==0:
            return False
    return True
n=int(input())
if isPrime(n):
    print(1)
    print(n)
elif isPrime(n-2):
    print(2)
    print('2 '+str(n-2))
else:
    print(3)
    for i in range(2,n-3):
        if i>2 and i%2==0:
            continue
        if n-3-i<i:
            break
        if isPrime(i) and isPrime(n-3-i):
            print('3 '+str(i)+' '+str(n-3-i))
            break

def isPrime(x) :
    if x == 1: return False
    if x == 2: return True
    if x%2 == 0: return False

    i = 3
    while i*i <= x :
        if x % i == 0 :
            return False
        i += 2
    return True
    
n = int(input())
if isPrime(n) :
    ans = [n]
else :
    bigPrime = 0
    for i in range(n-1, 0, -1) :
        if isPrime(i) :
            bigPrime = i
            break

    ans = [bigPrime]
    n -= bigPrime

    if isPrime(n) :
        ans.append(n)
    else :
        for i in range(1, n) :
            j = n - i
            if isPrime(i) and isPrime(j) :
                ans.append(i)
                ans.append(j)
                break

print(len(ans))
for i in ans :
    print(i, end = ' ')



import math


def prime(x):
    if x == 1:
        return False
    for i in range(2, math.floor(math.sqrt(x)) + 1):
        if x % i == 0:
            return False
    return True

n = int(input())

if prime(n):
    print(1)
    print(n)
elif prime(n - 2):
    print(2)
    print(n - 2, 2)
elif prime(n - 3):
    print(2)
    print(n - 3, 3)
else:
    x = n - 4
    while not prime(x):
        x -= 1

    rest = n - x

    y = rest - 1
    while not prime(y) or not prime(rest - y):
        y -= 1
    print(3)
    print(x, y, rest - y)


import math
n = int(input())
primes = [2]
for i in range(3, math.ceil(n ** 0.5) + 1):
    for p in primes:
        if i % p == 0:
            break
    else:
        primes.append(i)

def isprime(x): #x < n
    if x == 1: return False
    for p in primes:
        if x % p == 0 and x > p:
            return False
    else:
        return True

if isprime(n):
    print(1)
    print(n)
else:
    x1 = n
    while not isprime(x1):
        x1 -=2
    if isprime(n - x1):
        print(2)
        print(x1, n - x1)
    else:
        l = n - x1
        for x2 in primes:
            if isprime(l - x2):
                print(3)
                print(x1, x2, l - x2)
                break
        else:
            print('nu chto podelat...')


def main():
    n = int(input())
    limit = int(n ** .5) + 1
    lim12 = max(limit, 12)
    lim = lim12 // 6
    sieve = [False, True, True] * lim
    lim = lim * 3 - 1
    for i, s in enumerate(sieve):
        if s:
            p, pp = i * 2 + 3, (i + 3) * i * 2 + 3
            le = (lim - pp) // p + 1
            if le > 0:
                sieve[pp::p] = [False] * le
            else:
                break
    sieve[3] = True
    primes = [i for i, s in zip(list(range(3, lim12, 2)), sieve) if s]
    for i, p in enumerate((3, 5, 7)):
        primes[i] = p
    while primes and primes[-1] >= limit:
        del primes[-1]
    for x in n, n - 2, n - 4:
        for p in primes:
            if not x % p:
                break
        else:
            print((n - x) // 2 + 1)
            print(x, *([2] * ((n - x) // 2)))
            return
    for a in range(n // 2 | 1, n, 2):
        for p in primes:
            if not a % p:
                break
        else:
            for c in primes:
                b = n - a - c
                if b < 3:
                    break
                for p in primes:
                    if not b % p:
                        break
                else:
                    print(3)
                    print(a, b, c)
                    return


def __starting_point():
    main()

__starting_point()

def main():
    n = int(input())
    limit = int(n ** .5) + 1
    lim12 = max(limit, 12)
    lim = lim12 // 6
    l = [False, True, True] * lim
    lim = lim * 3 - 1
    for i, s in enumerate(l):
        if s:
            p, pp = i * 2 + 3, (i + 3) * i * 2 + 3
            le = (lim - pp) // p + 1
            if le > 0:
                l[pp::p] = [False] * le
            else:
                break
    l[3] = True
    primes = [i for i, s in zip(list(range(3, lim12, 2)), l) if s]
    for i, p in enumerate((3, 5, 7)):
        primes[i] = p
    res = False
    for x in n, n - 2, n - 4:
        if x > primes[-1]:
            for p in primes:
                if not x % p:
                    break
            else:
                res = True
        else:
            res = x in primes
        if res:
            print((n - x) // 2 + 1)
            print(x, *([2] * ((n - x) // 2)))
            return
    l = []
    for b in primes:
        l.append(b)
        for c in l:
            a = n - b - c
            for p in primes:
                if not a % p:
                    break
            else:
                print(3)
                print(a, b, c)
                return


def __starting_point():
    main()

__starting_point()

def main():
    n = int(input())
    limit = int(n ** .5) + 1
    lim12 = max(limit, 12)
    lim = lim12 // 6
    l = [False, True, True] * lim
    lim = lim * 3 - 1
    for i, s in enumerate(l):
        if s:
            p, pp = i * 2 + 3, (i + 3) * i * 2 + 3
            le = (lim - pp) // p + 1
            if le > 0:
                l[pp::p] = [False] * le
            else:
                break
    l[3] = True
    primes = [i for i, s in zip(list(range(3, lim12, 2)), l) if s]
    for i, p in enumerate((3, 5, 7)):
        primes[i] = p
    res = False
    for x in n, n - 2, n - 4:
        if x > primes[-1]:
            for p in primes:
                if not x % p:
                    break
            else:
                res = True
        else:
            res = x in primes
        if res:
            print((n - x) // 2 + 1)
            print(x, *([2] * ((n - x) // 2)))
            return
    l, cache = [], set()
    for b in primes:
        l.append(b)
        for c in l:
            a = n - b - c
            if a not in cache:
                for p in primes:
                    if not a % p:
                        cache.add(a)
                        break
                else:
                    print(3)
                    print(a, b, c)
                    return


def __starting_point():
    main()

__starting_point()

def mp():  return list(map(int,input().split()))
def lt():  return list(map(int,input().split()))
def pt(x):  print(x)
def ip():  return input()
def it():  return int(input())
def sl(x):  return [t for t in x]
def spl(x): return x.split()
def aj(liste, item): liste.append(item)
def bin(x):  return "{0:b}".format(x)
def printlist(l): print(' '.join([str(x) for x in l]))
def listring(l): return ''.join([str(x) for x in l])

def isPrime(n):
    if n == 2 or n == 3:
        return True
    if n < 2:
        return False
    if n % 2 == 0 or n % 3 == 0:
        return False
    if n < 10:
        return True
    p = 5
    while p <= int(n**0.5):
        if n % p == 0 or n % (p+2) == 0:
            return False
        p += 6
    return True
n = it()
if isPrime(n):
    print(1)
    print(n)
elif isPrime(n-2):
    print(2)
    print("2 %d" % (n-2))
else:
    r = 4
    while not isPrime(n-r):
        r += 2
    if r == 4:
        p,q = 2,2
    elif r == 6:
        p,q = 3,3
    elif r == 8:
        p,q = 3,5
    elif r == 10:
        p,q = 5,5
    elif r == 12:
        p,q = 5,7
    else:
        if isPrime(r-3):
            p,q = 3,r-3
        else:
            p = 5
            while not (isPrime(r-p) and isPrime(p)) and not (isPrime(r-p-2) and isPrime(p+2)):
                p += 6
            if isPrime(p) and isPrime(r-p):
                p,q = p,r-p
            else:
                p,q = p+2,r-p-2
    print(3)
    print("%d %d %d" % (n-r,p,q))