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

Poveste şi cerinţă...

Şcoala lui Pătraţel organizează meciul anual de fotbal. Cei doi capitani sunt Pătrăţel şi Triunghiuleţ. Ei îşi vor selecta echipele din cele $N$ clase ale şcolii. Selecţia echipelor funcţionează în felul următor:

h2. Date de intrare
 
Fişierul de intrare $football2.in$ ...

* Pătrăţel şi Triunghiuleţ aleg membrii alternativ, în ture. Pătrăţel începe.
* Într-o tură, pot fi aleşi doar elevi dintr-o singură clasă.
* Într-o tură, vor fi selectaţi cel puţin unul şi cel mult $K$ elevi.
* Într-o tură, se vor selecta cel mult la fel de mulţi elevi ca în tura precedentă.
* Căpitanul care selectează ultimul (sau ultimii) elevi primeşte premiul "Fo(1)tbal".

h2. Date de ieşire

Căpitanilor nu le pasă câţi elevi selectează, şi toţi elevii sunt identici când vine vorba de fotbal. Le pasă doar de premiul "Fo(1)tbal". Presupunând că amândoi au o strategie perfectă, cine câstigă premiul?

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

h2. Date de intrare

h2. Restricţii

Fişierul de intrare $football2.in$ va conţine mai multe teste, ce descriu scenarii diferite.
Pe prima linie a unui fişier veţi găsi $T$, numărul de teste. Apoi urmează descrierile testelor.
Pe prima linie a unui test veţi găsi $N$ şi $K$.
Pe a doua linie a unui test veţi găsi $N$ numere întregi pozitive, ce reprezintă mărimile claselor din şcoala lui Pătrăţel.
 
h2. Date de iesire
 
In fisierul de iesire $football2.out$ afişaţi răspunsurile pentru cele $T$ teste, pe un singur rând, fără spaţii între ele. Daca Pătrăţel câştigă premiul într-un test, afişaţi $1$; altfel, afişaţi $0$.
 
h2. Restrictii
 
* $T ≤ 100.000$
* Fie $SN$ suma valorilor lui $N$ pentru toate testele dintr-un fişier. Atunci $SN ≤ 100.000$
* $K, mărimea oricărei clase ≤ 1.000.000.000$
* Pentru $26$ de puncte, $K = 1$
* Pentru alte $8$ puncte, $N ≤ 10$, $SN ≤ 100$, $mărimea oricărei clase ≤ 3$.
* Pentru alte $11$ puncte $N ≤ 10$, $mărimea oricărei clase ≤ 5$.
* Pentru alte $8$ puncte, $N = 1$, $K, mărimea oricărei clase ≤ 100$.
* Pentru alte $16$ puncte, $N = 1$
* Pentru alte $16$ puncte $K = 2$
* Pentru alte $7$ puncte, $K$ e putere de $2$

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

h2. Exemple

h2. Exemplu

table(example). |_. football2.in |_. football2.out |

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

| 3
3 1
3 1 1
5 2
2 1 1 1 1
1 2
3|111}
 
h2. Explicatie
 
În primul test sunt 5 elevi în total, şi exact unul va fi selectat la fiecare tură (căci $K = 1$). Astfel, selecţia va dura exact 5 ture, şi ultimul student va fi selectat în tura lui Pătraţel. Astfel Pătrăţel câştigă.

h3. Explicaţie

În al doilea test, Pătrăţel poate mai întâi să selecteze doi elevi din prima clasa. Apoi, după încă patru ture în care fiecare capitan selectează câte un elev (căci toate clasele au doar un elev), Pătrăţel câştigă.

...

În al treilea test, Pătrăţel poate selecta iniţial un elev.

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