Fişierul intrare/ieşire:	tanakagame.in, tanakagame.out	Sursă	Empowersoft 2019
Autor	Tamio-Vesa Nakajima	Adăugată de	Tamio Vesa Nakajima •tamionv
Timp execuţie pe test	0.5 sec	Limită de memorie	256000 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Tanakagame

Tanaka va juca un joc cu prietenul său cel mai bun, Uivlis. Jocul decurge în felul următor:

1. Fie mulţimea P = {1} U {p | p e prim}
2. Se dă o matrice de N x M, şi un număr natural K.
3. Tanaka joaca primul
4. La tura lui X, se vor întâmpla următoarele:
   1. X selectează o poziţie în matrice.
   2. X scade din poziţia selectată orice număr din mulţimea P, astfel încât rezultatul e nenegativ.
   3. X selectează un drum de lungime cel mult K, care merge doar în dreapta şi în jos, începând de la poziţia selectată în pasii precedenti.
   4. Pentru toate poziţiile din drum, exceptând poziţia initial selectat, mai întâi X va adauga un număr din P, apoi va scădea oricare numar din P din poziţie, astfel încât rezultatul e nenegativ.
5. Cel care nu poate face o mutare valida pierde.

Cerinţa

Cunoscând starea iniţiale ale jocului să se determine cine câştigă, daca ambii jucatori joaca optim.

Date de intrare

Fişierul de intrare tanakagame.in conţine pe primul rând numarul de jocuri T, urmat de descrierile celor T jocuri.
Pe prima linie corespunzătoare unui test sunt 3 numere N, M, K cu semnificaţia din enunţ.
Urmatoarele N linii ale testului conţin câte M numere şi reprezintă valorile elementelor din matrice.

Date de ieşire

Fişierul de ieşire tanakagame.out conţine răspunsurile corespunzătoare jocurilor, fiecare răspuns pe câte o linie. Pentru fiecare joc se va afişa mesajul Tanaka dacă Tanaka căştigă, respectiv Uivlis dacă căştigă Uivlis.

Restricţii şi precizari

• 1 ≤ N, M ≤ 50
• 1 ≤ K ≤ 100
• 0 ≤ valorile din matrice ≤ 99
• 1 ≤ T ≤ 40
• Pentru 10 puncte, N = M = K = 1
• Pentru alte 10 puncte, N = 1, M = 2, K = 2
• Pentru alte 20 de puncte, N = 1, K = M
• Pentru alte 40 de puncte, K = 100

Exemplu

Cum se trimit solutii?