kboard

Kboard

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

Gigel si Ionel au inceput sa joace un joc nou, dupa ce s-au plictisit de jocul de la Happy Coding-ul de anul trecut ( vezi problema 'obj':problema/obj ). De data aceasta, ei au la dispozitie o tabla liniara formata din $N$ patratele numerotate de la $1$ la $N$, de la stanga la dreapta. Initial, toate cele $N$ patratele sunt libere. Cei doi efectueaza alternativ mutari de tipul urmator: jucatorul aflat la mutare trebuie sa amplaseze o piesa avand dimensiunea $1xK$ peste $K$ patratele consecutive libere de pe tabla; in urma amplasarii piesei, cele $K$ patratele devin ocupate. Castigatorul jocului este cel care efectueaza ultima mutare (echivalent, pierzatorul este jucatorul care, atunci cand ii vine randul, nu mai poate efectua nici o mutare).

Gigel si Ionel au inceput sa joace un joc nou, dupa ce s-au plictisit de jocul de la Happy Coding-ul de anul trecut ( vezi problema 'obj':problema/obj ). De data aceasta, ei au la dispozitie o tabla de joc liniara formata din $N$ patratele numerotate de la $1$ la $N$, de la stanga la dreapta. Initial, toate cele $N$ patratele sunt libere. Cei doi efectueaza alternativ mutari de tipul urmator: jucatorul aflat la mutare trebuie sa amplaseze o piesa avand dimensiunea $1xK$ peste $K$ patratele consecutive libere de pe tabla; in urma amplasarii piesei, cele $K$ patratele devin ocupate. Castigatorul jocului este cel care efectueaza ultima mutare (echivalent, pierzatorul este jucatorul care, atunci cand ii vine randul, nu mai poate efectua nici o mutare).

Pentru mai multe perechi $(K,N)$ date, determinati cine castiga jocul (primul jucator, adica cel care efectueaza prima mutare, sau cel de-al doilea), considerand ca ambii jucatori vor folosi o strategie optima.

h2. Restrictii
* $1 ≤ K ≤ 10 000 000$

* $1 ≤ T ≤ 100 000$

* Daca $K ≤ 2$, atunci $1 ≤ N ≤ 1 000 000 000$
* Daca $K > 2$, atunci $1 ≤ N ≤ max{3000, 69*K-19}$

h2. Exemplu

h2. Exemple

table(example). |_. kboard.in |_. kboard.out |
|1 3
1
2
3

|1
2
1
|
|2 4
1
2
5
6
|2
1
2
1

|

|3 4
999
998
100
256
|1

1
2
1

|

|
|9999999 20
89999988
289999962
129999982
16124217
299106936
60546243
524323847
649999916
449756549
64633851
209999972
368724199
152731683
89999988
77390991
649999916
25493701
289999962
225376567
223888509
|2
2
2
1
1
1
1
2
1
1
2
1
1
2
1
2
1
2
1
1
|

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

2376