Ion si Vasile joaca un nou joc. Ei au la
dispozitie o tabla dreptunghiulara de dimensiuni NxM.
Liniile sunt numerotate de la 1 la N, de sus in jos, iar coloanele
de la 1 la M,
de la stanga la dreapta. Jucatorii efectueaza mutari alternativ,
regula jocului fiind urmatoarea:
Jucatorul aflat
la mutare pozitioneaza o piesa pe un patratel liber de pe tabla
de joc. Daca in urma pozitionarii piesei exista pe o coloana trei
piese adiacente jucatorul castiga si jocul se termina, altfel,
jocul continua
Se stie ca Ion muta intotdeauna primul. Intr-o zi
cei doi au gasit o tabla de joc care avea deja cateva piese
plasate in unele patratele. Acest lucru nu ii deranjeaza insa pe
cei doi si se decid sa inceapa jocul luand in considerare si
piesele deja existente pe tabla.
Cerinţă
Stiind ca atat Ion, cat si Vasile joaca optim si
ca Ion muta intotdeauna primul, determinati jucatorul care castiga
jocul.
Date de intrare
Fişierul de ieşire connect3.in
conţine pe prima linie numarul natural T,
reprezentand numarul de teste ce urmeaza a fi descrise. Prima
linie a unui test va contine trei numere naturale N, M si K,
reprezentând numarul de linii ale tablei de joc,
numarul de coloane ale tablei de joc si respectiv numarul de piese
care sunt deja pozitionate pe tabla de joc. Urmeaza K linii, fiecare continand cate doua numere naturale x si y reprezentand linia, respectiv
coloana pe care se afla o piesa pe tabla de joc.
Date de ieşire
Fişierul de ieşire connect3.out
va conţine T linii, pe fiecare
fiind scris Ion sau Vasile,
reprezentand numele celui care a castigat jocul. Pe linia i se va afla numele castigatorului pentru al i-lea
test din fisierul de intrare.
Restricţii
1
<= T <= 10
1
<= N <= 1000
1
<= M <= 2 000 000 000
0
<= K <= 100 000
Toate datele din
fisierul de intrare sunt consistente, adica nu se gasesc doua sau
mai multe piese in acelasi patratel si nu exista trei sau mai
multe piese adiacente pe nicio coloana.
Exemple
connect3.in
connect3.out
2
3
1 0
3 1 1
1 1
Ion
Vasile
stud. Adrian Airinei
Facultatea de Informatica, Universitatea "Al. I. Cuza"
Iaşi