Gigel şi Ionel se joacă cu cuburile. Ei au la dispoziţie o mulţime de cuburi de dimensiune egală pe care le-au aranjat în n turnuri. Cele n turnuri sunt aşezate pe masă şi sunt formate din a1, a2, ..., an cuburi de dimensiuni egale.
Gigel şi Ionel modifică aceste turnuri, singura mişcare posibilă
fiind luarea alternativă a unui cub dintr-un turn oarecare. În cazul în care cubul
luat se află undeva la mijlocul turnului, toate cuburile de deasupra lui "cad" (deoarece nu se mai sprijină pe nimic).
Pierde cel care nu mai poate lua un cub.
Cerinţă
Date n, a1, a2, ..., an şi cine începe jocul (G sau I), şi presupunând
că fiecare joacă perfect, să se determine cine va câştiga jocul (G sau I).
Date de intrare
Prima linie a fişierului de intrare joct.in conţine un număr natural J, care reprezintă numărul de jocuri. Fiecare dintre următoarele 3 linii descriu un joc, astfel: prima linie dintre cele 3 conţine un număr natural n, reprezentând numărul de turnuri; a doua linie dintre cele 3 conţine n numere naturale a1, a2, ..., an, separate prin câte un spaţiu, reprezentând în ordine, numărul de cuburi din cele n turnuri; linia a treia conţine unul dintre caracterele literă mare G sau I, indicând persoana care începe jocul (Gigel sau Ionel).
Date de ieşire
Fişierul de ieşire joct.out va conţine J linii, corespunzătoare celor J jocuri, pe fiecare linie fiind unul dintre caracterele G sau I, indicând câştigătorul jocului respectiv.
Restricţii
1 < J < 11
0 < n < 100
0 < ai < 2000000000, pentru 1<=i<=n
Exemplu
joct.in
joct.out
Explicaţii
Exemple derulare joc
4
2
4 4
G
3
3 4 5
G
3
15 19 7
I
3
15 8 7
G
I
G
I
I
4 Jocuri
2 turnuri în primul joc
cele două turnuri au câte 4 cuburi începe Gigel
3 turnuri în jocul 2 acestea au respectiv 3, 4 şi 5 cuburi începe Gigel
3 turnuri în jocul 3 acestea au respectiv 15, 19 şi 7 cuburi începe Ionel
3 turnuri în jocul 4 acestea au respectiv 15, 8 şi 7 cuburi începe Gigel
Joc 1: A x y - înseamnă A ia x cuburi din turnul y
G 1 1; I 1 2; G 1 1; I 1 2; G 2 1; I 2 2 ... G pierde
Joc 2: G 2 1; I 4 2; G 4 3; I 1 1; G 1 3 ... I pierde
Joc 3: I 11 2; G 8 2; I 8 1; G 2 1; I 2 3; G 5 1; I 5 3 ... G pierde