PRIMOVV - Primo Va Primo Viene

Un número entero positivo k, se define como primovv, si puede ser obtenido como resultado de la suma de algunos de los números primos en 2..100, -no puede haber elementos repetidos en dicha suma-.

Ej.: 48 es primovv, porque 48= 2 + 3 + 43

                              ó porque 48 = 5 + 43

A positive integer number k, is defined as primovv if the can be obtained as the result of the sum of some prime numbers in 2..100, -the sum has no repeated elements-.

Example: 48 is primobb, because 48= 2 + 3 + 43

   or because 48 = 5 + 43

Input

Cada línea de la entrada consta de un entero k, (k>1). Cada línea es un caso diferente para informar. La entrada termina con una línea conteniendo el valor 0, el cual no se procesa.

Each line of the input have an integer k, (k>1). Each line is a different case to inform. The input ends with a line containing the value 0 (this value is the end of data signal, and won't be processed).

Output

Por cada línea de la entrada, se debe informar “True” (ó “False”) si el número es (ó no es) primovv. En caso de que sea primovv, también hay que informar la suma (de menor cantidad de sumandos posibles) que permite obtenerlo, con sus sumandos ordenados descendentemente. (si existen más de una suma -de cantidad mínima de sumandos- que generan el número, se debe informar la que tenga el mayor de los sumandos).

Your program must to generate one output line, for each input line, showing "True" (or "False") if the number is (or no) primovv. In the case the number be a primovv, you have to display the sum (with the smallest possible numbers of summands) to obtain it, with the summands descendingly ordered. (if there are more than one possible sum -with the smallest possible numbers-, you must to inform the one with the greater summand). 

Sample Input

48
4
7
269

1500
0
Sample Output


True 43 5
False
True 7
True 97 89 83
False

 


Added by:Coach UTN FRSF
Date:2011-06-09
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2014-05-23 03:40:17 Mitch Schwartz
Agreed that the constraints should have been higher to make a good classical problem, so I think this should stay in tutorial. I have no idea whether it's a (near) duplicate of an existing problem.
2014-05-22 20:26:41 Francky
I think it could be a nice classical task with higher constraints ; but I think there's yet such a task ; can't remember which problem... Let's see other comments, but maybe to tutorial for me.
2014-05-22 19:11:31 Mitch Schwartz
This is maybe more appropriate for tutorial than classical, moved there temporarily until I have time to decide (I'm busy now).
2014-05-22 19:04:50 Mitch Schwartz
No mention of scoring, so presumably the psetter has no idea what the challenge section is; moved to classical.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.