== include(page="template/taskheader" task_id="kpart") ==

Poveste şi cerinţă...

Virgil tocmai şi-a propus să studieze proprietăţi ale şirurilor. Astfel, el defineşte un $K-şir$ ca fiind orice şir de numere naturale nenule care are proprietatea că orice subsecvenţă a sa de lungime $K$ se poate partiţiona în două subşiruri disjuncte, nu neapărat subsecvenţe, având suma egală. De exemplu $1, 2, 1, 3$ este un $3-şir$, căci $1, 2, 1$ poate fi partiţionat în $1, 1$ şi $2$, şi $2, 1, 3$ poate fi partiţionat în $2, 1$ şi $3$. Nu este $2-şir$ căci $1, 2$ nu poate fi partiţionat în două subşiruri cu sumă egală. Totodată nu este $4-şir$
 
Pentru $T$ şiruri de numere naturale nenule $A$, Virgil doreşte să afle toate valorile $K$, pentru care şirul $A$ poate fi numit $K-şir$.
 

h2. Date de intrare

Fişierul de intrare $kpart.in$ ...

Pe prima linie a fişierul de intrare $kpart.in$ se află numărul $T$. Urmează apoi $T$ şiruri. Fiecare şir este dat prin două linii. Prima linie conţine valoarea lui $N$. $A$ doua linie conţine elementele şirului separate prin câte un spaţiu.

h2. Date de ieşire

În fişierul de ieşire $kpart.out$ ...

În fişierul de ieşire $kpart.out$ afişaţi răspunsurile pentru fiecare şir în ordine. Pentru fiecare şir afişaţi câte o linie care conţine mai întâi numărul de valori $K$ pentru care şirul este $K-şir$ şi apoi, în ordine crescătoare, acele valori $K$ pentru care şirul este $K-şir$.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ T  ≤ 20$
* Fie $S$ suma valorilor dintr-un şir (nu suma valorilor tuturor şirurilor). Atunci $1 ≤ S ≤ 100 000$
* În plus:
table(restrictii). |_. # |_. Punctaj |_. Restricţii |
| 1 | 10 | 1 ≤ N ≤ 30 |
| 2 | 20 | 31 ≤ N ≤ 120 |
| 3 | 70 | 121 ≤ N ≤ 1 000 |
 

h2. Exemplu
table(example). |_. kpart.in |_. kpart.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 2
  7
  7 3 5 1 3 3 5
  6
  1 2 3 5 8 3
| 2 4 6
  2 3 6

|
h3. Explicaţie

...

Primul şir, cel de lungime $7$ este $4-şir$ şi $6-şir$, deoarece fiecare secvenţă de lungime $4$, respectiv $6$, conţin câte două subşiruri disjuncte cu suma egală care partiţionează secvenţa. Al doilea şir, cel de lungime $6$ este $3-şir$ şi $6-şir$, deoarece fiecare secvenţă de lungime $3$ şi fiecare secvenţa de lungime $6$, conţin câte două subşiruri disjuncte cu suma egală care partiţionează secvenţa.

== include(page="template/taskfooter" task_id="kpart") ==