Asa cum se stie, Gigel este mare amator de probleme. Nu are importanta daca problema e cu siruri de caractere sau cu numere. Dacã problema cere ingeniozitate pentru rezolvare, Gigel se apucã imediat de ea. Asa s-a intamplat si cu urmatoarea problema: a scris pe hartie mai multe numere naturale si a observat ca unele sume partiale ale acestor numere se divid cu 3 in timp ce alte sume partiale nu se divid. Gigel si-a pus prin urmare problema astfel: daca am un sir de n numere naturale, care este numarul maxim de elemente ale acestui sir a caror sumã se divide cu 3?

Cerinţă

Fiind dat un sir de n numere naturale, determinati numarul maxim de elemente ale sirului a cãror sumã se divide cu 3. Determinati de asemenea elementele care nu fac parte din sumã.

Date de intrare

Fişierul de intrare trei.in conţine pe prima linie numãrul natural n. Pe fiecare dintre urmãtoarele n linii se aflã câte un numãr natural.

Date de ieşire

Fişierul de ieşire trei.out va conţine pe prima linie un numãr natural k reprezentând numarul maxim de elemente ale sirului a caror suma se divide cu 3. Pe linia a doua se vor afla n-k valori naturale, separate prin câte un spatiu, reprezentând valorile din sir care nu fac parte din suma.

Restricţii

• 1<=n<=200000
• 0<=Elementele sirului<=2000000000

Exemple

trei.in	trei.out	Explicaţii
7 10 6 7 12 4 7 22	5 10 7	Numarul maxim de elemente a caror suma se divide cu 3 este 5. Aceste elemente sunt: 6 12 4 7 22 Elementele care nu fac parte din suma sunt 10 si 7

prof. Marinel Serban

Liceul de Informatică „Grigore Moisil” Iaşi

marinel_serban@yahoo.com