În drumul lor către oraşul Zalău, Bulănel şi Bulăniţa au hotărât să joace un joc pentru a alunga plictiseala.

Cei doi au la dispoziţie un grid cu N linii (numerotate de la 1 la N) şi M coloane (numerotate de la 1 la M). Bulănel începe jocul prin plasarea unui pătrat pe o celulă a gridului. Scopul jocului este acoperirea gridului înaintea celuilalt jucător. La fiecare pas, un jucător alege o direcţie (nord, est, sud, vest) si extinde figura rectangulară în direcţia respectivă cu maxim K linii (dacă direcţia aleasă a fost nord sau sud) sau maxim K coloane (dacă direcţia aleasă a fost est sau vest). La nici un moment al jocului, nu se poate extinde figura în afara gridului. Jucătorul care nu mai poate extinde figura în nicio direcţie este declarat pierzător. După ce Bulănel plasează pătratul iniţial, Bulăniţa e cea care face prima extindere.

Cei doi au la dispoziţie un grid cu $N$ linii (numerotate de la $1$ la $N$) şi $M$ coloane (numerotate de la $1$ la $M$). Bulănel începe jocul prin plasarea unui pătrat pe o celulă a gridului. Scopul jocului este acoperirea gridului înaintea celuilalt jucător. La fiecare pas, un jucător alege o direcţie (nord, est, sud, vest) si extinde figura rectangulară în direcţia respectivă cu maxim $K$ linii (dacă direcţia aleasă a fost nord sau sud) sau maxim $K$ coloane (dacă direcţia aleasă a fost est sau vest). La nici un moment al jocului, nu se poate extinde figura în afara gridului. Jucătorul care nu mai poate extinde figura în nicio direcţie este declarat pierzător. După ce Bulănel plasează pătratul iniţial, Bulăniţa e cea care face prima extindere.

De exemplu, dacă ar juca pe un grid de N = 3 linii şi M = 5 coloane şi ar alege K = 3, jocul s-ar putea desfăşura în felul următor:

De exemplu, dacă ar juca pe un grid de $N = 3$ linii şi $M = 5$ coloane şi ar alege $K = 3$, jocul s-ar putea desfăşura în felul următor:

| !problema/aiacujoc?01.jpg! | !problema/aiacujoc?02.jpg! | !problema/aiacujoc?03.jpg! |

| Pasul 1: Bulănel plasează pătratul pe linia 2, coloana 5 | Pasul 2: Bulăniţa extinde figura cu 2 coloane în vest. | Pasul 3: Bulănel extinde figura cu 1 linie în nord. |

| *Pasul 1*: Bulănel plasează pătratul pe linia $2$, coloana $5$ | *Pasul 2*: Bulăniţa extinde figura cu $2$ coloane în vest. | *Pasul 3*: Bulănel extinde figura cu $1$ linie în nord. |

| !problema/aiacujoc?04.jpg! | !problema/aiacujoc?05.jpg! | !problema/aiacujoc?06.jpg! |

| Pasul 4: Bulăniţa extinde figura cu 1 linie în sud. | Pasul 5: Bulănel extinde figura cu 1 coloană în vest. | Pasul 6: Bulăniţa extinde figura cu 1 coloană în vest. |

| *Pasul 4*: Bulăniţa extinde figura cu $1$ linie în sud. | *Pasul 5*: Bulănel extinde figura cu $1$ coloană în vest. | *Pasul 6*: Bulăniţa extinde figura cu $1$ coloană în vest. |

Bulănel pierde jocul acesta din cauză că nu mai poate extinde figura în nici o direcţie. Totuşi, Bulănel ar fi putut câştiga jocul dacă ar fi făcut o serie diferită de mişcări (de exemplu, dacă ar fi extins figura cu 2 coloane în vest în loc de 1, în pasul 5) sau dacă ar fi plasat pătratul iniţial pe o altă poziţie.

Bulănel pierde jocul acesta din cauză că nu mai poate extinde figura în nici o direcţie. Totuşi, Bulănel ar fi putut câştiga jocul dacă ar fi făcut o serie diferită de mişcări (de exemplu, dacă ar fi extins figura cu $2$ coloane în vest în loc de $1$, în pasul 5) sau dacă ar fi plasat pătratul iniţial pe o altă poziţie.

h2. Cerinţă

h2. Date de intrare

Fişierul de intrare aiacujoc.in conţine pe prima linie numărul natural T, reprezentând numărul de jocuri pe care Bulănel şi Bulăniţa o să-l joace. Pe fiecare din următoarele T linii, se află câte trei numerele naturale care definesc un joc: numărul natural N, reprezentând numărul de linii ale gridului, urmat de numărul natural M, reprezentând numărul de coloane ale gridului, urmat de numărul natural K, reprezentând numărul de linii sau de coloane cu care un jucător poate extinde figura la un anumit pas.

Fişierul de intrare $aiacujoc.in$ conţine pe prima linie numărul natural $T$, reprezentând numărul de jocuri pe care Bulănel şi Bulăniţa o să-l joace. Pe fiecare din următoarele $T$ linii, se află câte trei numerele naturale care definesc un joc: numărul natural $N$, reprezentând numărul de linii ale gridului, urmat de numărul natural $M$, reprezentând numărul de coloane ale gridului, urmat de numărul natural $K$, reprezentând numărul maxim de linii sau de coloane cu care un jucător poate extinde figura la un anumit pas.

h2. Date de ieşire

Fişierul de ieşire aiacujoc.out va conţine T linii. Pe fiecare linie i, se va afla câte un număr natural care reprezintă numărul de poziţii de pe grid unde Bulănel poate plasa pătratul iniţial, care îi asigură lui Bulănel strategie câştigătoare pentru al i-lea joc.

Fişierul de ieşire $aiacujoc.out$ va conţine $T$ linii. Pe fiecare linie $i$, se va afla câte un număr natural care reprezintă numărul de poziţii de pe grid unde Bulănel poate plasa pătratul iniţial, care îi asigură lui Bulănel strategie câştigătoare pentru al $i$-lea joc.

h2. Restricţii

* Pentru toate testele, 1 ≤ T ≤ 10.
* Pentru teste în valoare de 5 puncte, N = 1, 1 ≤ M ≤ 20, K ≥  max(N, M).
* Pentru alte teste în valoare de 5 puncte, 1 ≤ N, M ≤ 20, K ≥ max(N, M), N şi M au parităţi diferite.
* Pentru alte teste în valoare de 10 puncte, 1 ≤ N, M ≤ 20, K ≥ max(N, M).
* Pentru alte teste în valoare de 30 de puncte, 1 ≤ N, M ≤ 1 000, K ≥ max(N, M).
* Pentru alte teste în valoare de 10 de puncte, 1 ≤ N, M ≤ 1 000 000, K ≥ max(N, M).
* Pentru alte teste în valoare de 20 de puncte, 1 ≤ N, M, K ≤ 1 000 000.
* Pentru alte teste în valoare de 10 de puncte, 1 ≤ N, M ≤ 1 000 000 000, 1 ≤ K ≤ 1 000 000.

* Pentru toate testele, $1 ≤ T ≤ 10$.
* Pentru teste în valoare de $5$ puncte, $N = 1$, $1 ≤ M ≤ 20$, $K ≥ max(N, M)$.
* Pentru alte teste în valoare de $5$ puncte, $1 ≤ N, M ≤ 20$, $K ≥ max(N, M)$, $N$ şi $M$ au parităţi diferite.
* Pentru alte teste în valoare de $10$ puncte, $1 ≤ N, M ≤ 20$, $K ≥ max(N, M)$.
* Pentru alte teste în valoare de $30$ de puncte, $1 ≤ N, M ≤ 1 000$, $K ≥ max(N, M)$.
* Pentru alte teste în valoare de $10$ de puncte, $1 ≤ N, M ≤ 1 000 000$, $K ≥ max(N, M)$.
* Pentru alte teste în valoare de $20$ de puncte, $1 ≤ N, M, K ≤ 1 000 000$.
* Pentru alte teste în valoare de $10$ de puncte, $1 ≤ N, M ≤ 1 000 000 000$, $1 ≤ K ≤ 1 000 000$.

* Ambii jucători joacă optim ceea ce înseamnă că nu fac greşeli, anticipează mişcările adversarului, iar dacă există o strategie de mişcări care să-i conducă spre câştig atunci o vor folosi.

* Problema va fi evaluată pe teste în valoare de 90 de puncte.
* Se vor acorda 10 puncte din oficiu.

* Problema va fi evaluată pe teste în valoare de $90$ de puncte.
* Exemplele vor reprezenta teste în valoare de $10$ ("puncte din oficiu") şi vor fi cu feedback.

h2. Exemplu

h3. Explicaţie

...

h4. Primul exemplu
 
Pentru primul joc, gridul are dimensiunile $N=3, M=5$. Un jucător poate extinde figura cu maxim $K=5$ linii sau coloane. Poziţiile care îi asigură lui Bulănel strategie de câştig sunt $(1;2), (1;4), (2;3), (3;2), (3;4)$.
Pentru al doilea joc, gridul are dimensiunile $N=88, M=200$. Un jucător poate extinde figura cu maxim $200$ de linii sau coloane. Sunt $320$ de poziţii care conduc la câştig.
 
h4. Al doilea exemplu
 
Pentru primul joc, gridul are dimensiunile $N=3, M=5$. Un jucător poate extinde figura cu maxim $K=3$ linii sau coloane. Poziţiile care îi asigură lui Bulănel strategie de câştig sunt $(1;2), (1;4), (2;1), (2;3), (2;5), (3;2), (3;4)$.
Pentru al doilea joc, gridul are dimensiunile $N=88, M=200$. Un jucător poate extinde figura cu maxim $56$ de linii sau coloane. Sunt $680$ de poziţii care conduc la câştig.

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