# -*- coding: utf-8 -*-
def rwh_primes2(n):
    # https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    """ Input n>=6, Returns a list of primes, 2 <= p < n """
    correction = (n % 6 > 1)
    n = {0: n, 1: n-1, 2: n+4, 3: n+3, 4: n+2, 5: n+1}[n % 6]
    sieve = [True] * (n/3)
    sieve[0] = False
    for i in xrange(int(n**0.5)/3+1):
        if sieve[i]:
            k = 3*i+1|1
            sieve[((k*k)/3)::2*k]=[False]*((n/6-(k*k)/6-1)/k+1)
            sieve[(k*k+4*k-2*k*(i & 1))/3::2*k] = [False]*((n/6-(k*k+4*k-2*k*(i & 1))/6-1)/k+1)
    return [2, 3] + [3*i+1 | 1 for i in xrange(1, n/3-correction) if sieve[i]]


def represent_as_3primes(k, primes):
    result1 = []
    result2 = []
    if k % 2 == 0:
        k -= 2
        result1.append(2)
        result2.append(2)
    else:
        k -= 3
        result1.append(3)
        result2.append(3)
    for i in primes:
        if k - i in primes:
            if len(result1) == 1:
                result1.append(i)
                result1.append(k-i)
            else:
                result2.append(i)
                result2.append(k - i)
                return result1, result2
