Fişierul intrare/ieşire:	piese2.in, piese2.out	Sursă	Algoritmiada 2009, Runda 1
Autor	Andrei Grigorean	Adăugată de	Andrei Grigorean •wefgef
Timp execuţie pe test	0.425 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Piese2

Miruna si Aglaia au primit de Mos Nicolae din partea parintilor un joc cu piese colorate. Acesta consta din K piese rosii, K piese albastre si o tabla de joc de dimensiune 1 x N. Regulile jocului sunt urmatoarele:

• La inceput se pozitioneaza piesele pe tabla astfel incat sa nu existe 2 piese pe aceeasi coloana, iar oricare 2 piese consecutive sa fie colorate distinct. Prima piesa trebuie sa fie rosie.
• Cele doua fetite vor efectua mutari alternativ, pana cand una dintre ele nu va mai putea efectua nicio mutare, moment in care ea va pierde jocul.
• Miruna poate muta doar piese rosii, iar Aglaia doar piese albastre.
• O mutare consta din alegerea unei piese si deplasarea ei o coloana spre dreapta sau spre stanga daca nu se paraseste tabla si daca respectiva locatie nu este ocupata de alta piesa.
• Miruna este cea care efectueaza prima mutare.

Fetitele sunt foarte inteligente, asa ca ele vor juca intotdeauna optim. Pentru o configuratie initiala a pieselor, va trebui sa aflati cine va castiga jocul.

Date de intrare

Fişierul de intrare piese2.in contine pe prima linie 3 numere naturale T, N si K, reprezentand numarul de teste ce vor urma, dimensiunea tablei de joc, respectiv numarul de piese de o anumita culoare. Urmatoarele T linii vor contine cate 2 * K numere naturale. Acestea vor fi distincte si se vor da in ordine crescatoare. Ele vor reprezenta pozitiile initiale ale pieselor.

Date de ieşire

În fişierul de ieşire piese2.out veti afisa T linii, pe linia i aflandu-se numele fetitei castigatoare pentru jocul cu numarul i.

Restricţii

• 1 ≤ T ≤ 10
• 2 ≤ N ≤ 10⁹
• 1 ≤ K ≤ 10⁵
• 2*K ≤ N
• Pentru 20% din teste N ≤ 10

Exemplu

Explicaţie

Avem o tabla de lungime 4, si cate o piese din fiecare culoare. In primul joc Miruna muta pe 2, Aglaia muta pe 4, Miruna pe 3 si castiga. In al doilea joc Miruna muta pe 2, Aglaia pe 3, Miruna pe 1, Aglaia pe 2 si castiga.

Cum se trimit solutii?