Táto úloha je programátorská. Ako svoje riešenie odovzdaj program vo svojom obľúbenom jazyku a automaticky sa dozvieš, koľko si dostal(a) bodov. Ak si takýto typ úloh ešte nikdy neriešil(a), skús sa pozrieť ako by mal vyzerať ideálny program. Ak zatiaľ programovať nevieš, ale chcel(a) by si sa naučiť, môžeš skúsiť našu KSP School.

Lucka a Miško sa hrajú hru. Lucka je ale úplne zaneprázdnená tým že robí ťahy, a teda nemá čas na rozmýšlanie nad tým, ktorý ťah sa oplatí spraviť. Na to tu ste práve vy. Pomôžte Lucke vybrať správny ťah.

Úloha

Miško a Lucka sa hrajú hru. Majú plánik, na ktorom je v rade za sebou niekoľko políčok. Na prvom políčku stojí figúrka. Na každom políčku je napísané číslo, ktoré hovorí, ako ďaleko je toto políčko od cieľa (teda v cieli je 0). Miško a Lucka sa striedajú v ťahoch, Lucka začína. Hráč na ťahu musí pohnúť figúrku o nejaký počet políčok dopredu. Navyše nemôžu figúrku posunúť o presne toľko políčok, ako bola posunutá v minulom (súperovom) ťahu. Keď hráč na ťahu nemôže spraviť ťah, tak prehrá, teda ten druhý hráč vyhrá.

Vašou úlohou je zistiť, či Lucka dokáže Miška poraziť, alebo či vie Miško vyhrať bez ohľadu na to, ako dobre bude Lucka hrať. Následne, ak Lucka dokáže vyhrať, musíte Miška poraziť.

Formát vstupu a výstupu

Ako prvé musí váš program vypísať hram alebo nechaj ma. Tým určíte, či váš program bude hrať proti Miškovi, alebo len zistí, či Lucka dokáže Miška poraziť alebo nie.

Následne váš program dostane ako vstup parametre hry. Na prvom riadku vstupu je jedno číslo $n$ - počiatočná pozícia figúrky. Na ďaľšom riadku je jedno číslo $k$ - počet dovolených ťahov. Nasleduje $k$ riadkov, každý obsahujúci číslo $a_i$ jeden z povolených ťahov. Platí, že $1 \leq a_i \leq n$.

Následne váš program musí vypísať vyhrala som alebo prehrala som, podľa toho, či Lucka dokáže Miška poraziť, alebo nie. Ak nechcete hru hrať (vypísali ste na začiatku nechaj ma), tak váš program musí skončiť. V opačnom prípade, ak Lucka dokáže vyhrať, musíte poraziť Miška. Váš program začína, musí vypísať o koľko políčok chcete posunúť figúrku. Potom načíta o koľko políčok Miško posunul figúrku. Potom je opäť váš ťah, a musíte vypísať o koľko políčok chcete posunúť figúrku. Pozor v prípade že Miško už po vašom ťahu nedokáže spraviť žiaden ťah, musí váš program skončiť.

Aby testovanie fungovalo ako má, je nutné po vypísaní každého riadku flushnúť výstup, aby ho testovač uvidel. V C++ by malo stačiť cout << nieco << endl;, ale môžete explicitne použiť príkaz cout.flush();. V Pythone vypisujte príkazom print(cislo, flush=True) alebo po vypísaní zavoljate sys.stdout.flush(). Pre iné jazyky hľadajte ekvivalent k príkazu flush.

Hodnotenie

Bude 6 sád vstupov. 4 normálne, a dve (piata a šiesta) bonusové. V sadách 1, 3 a 5 stačí na získanie bodov, keď váš program zistí, či Lucka dokáže Miška poraziť. V ostatných sadách musíte hru aj hrať.

V jednotlivých sadách navyše platia nasledovné obmedzenia:

Príklad

<<< hram
>>> 5
>>> 3
>>> 1
>>> 2
>>> 3
<<< vyhrala som
<<< 1
>>> 2
<<< 1

Tento program na začiatku vypíše, že chce hru aj hrať. Dostane teda popis hry: figúrka je na začiatku na políčku $5$ a môžu sa robiť $3$ rôzne ťahy: $1$, $2$ a $3$. Program zistí, že Lucka vie vyhrať, a spraví prvý ťah - posunie figúrku o 1 políčko, teda na políčko $4$. Potom Miško posunie figúrku o $2$, na políčko $2$. Lucka posunie figúrku o $1$ na políčko $1$. Miško už nemôže spraviť ťah, lebo by mohol posunúť len o $1$ políčko, ale to bol aj Luckin ťah predtým, takže ho nemôže zopakovať. Lucka teda vyhrala a program skončí.

Znaky <<< a >>> sú len na ilustráciu, aby bolo v príklade vidieť, čo je vstup a čo výstup. V skutočnosti sa na vstupe ani výstupe nevyskytujú.