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

_Această problemă este numită Petrick - şi acest lucru nu trebuie confundat cu numele autorului. Petrick se referă la "trick", un sinonim pentru frazele româneşti "pe smecherie" sau "pe barosaneala". Trick-ul real se referă la a vedea dacă tu, un uimitor jucător de şah, poţi câştiga împotriva adversarului într-o singură mişcare (aminteste-ti că esti un talentat!)._
 
În mod formal, ti se dă o tabla de şah *fără pioni*, cu $N$ piese pe ea şi ti se cere să vezi dacă albul ii poate da sah-mat negrului prin mutarea unei *singure* piese. Reţine că starea tablei de şah poate fi generata într-un joc ipotetic de şah, în conformitate cu regulile bine cunoscute ale şahului.
 
_Urmeaza o scurtă descriere a jocului de şah. Şahul este un joc jucat pe o tablă pătrată de $8$ x $8$, cu diferite piese. Piesele sunt regi, regine, nebuni, cai, sau ture. Fiecare piesă poate fi neagra sau alba, iar fiecare piesă se poate afla pe o singură celulă. Nu poate fi mai mult de o piesa intr-o celulă. Fiecare piesă poate, în funcţie de tipul său, să se deplaseze la alte celule; în special:_
 
# Regele se poate muta în orice celulă adiacenta (verticala, orizontala sau diagonala).
# Tura poate să se deplaseze ortogonal în sus, în jos, în stânga sau în dreapta pe oricare distanţă, atâta timp cât nu "sare peste" alte piese.
# Nebunul poate muta în diagonală pe orice distanţă, atâta timp cât nu "sare peste" alte piese.
# Regina poate realiza orice mutare pe care un nebun sau o tura o pot face.
# Calul se poate muta ortogonal în sus, în jos, în stânga sau în dreapta cu două celule, mutare urmată imediat de o mişcare suplimentară de o celula perpendiculare pe ultima (în forma literei mari *L*); calul poate "sări peste" alte piese.
 
_Există exact un rege al fiecărei culori._
_Există cel mult două ture, nebuni şi cai de fiecare culoare._
_Dacă există doi nebuni de aceeaşi culoare, atunci se garantează ca suma paritatilor pozitiilor celulelor pe care acestia sunt situati este diferita._
_O piesă nu se poate muta într-o celulă care conţine o piesa de aceeaşi culoare. Dacă o piesă se mişcă într-o celulă unde se afla o piesa de culoarea opusă, atunci piesa care se afla pe celula iniţiala este scoasă din joc._
_Spunem că o culoare este în *check* (adica sah) dacă şi numai dacă o piesa de culoarea opusă s-ar putea muta în celula care conţine regele acelei culori. Nu este permis ca o piesa sa faca o mutare invalida._
_Spunem că o culoare este în *check-mate* (sah-mat) dacă şi numai dacă este in *check* (sah) şi nu poate face mişcări valide._
 
Acum, este necesar să descoperi dacă albul poate face o mişcare valida care pune negrul în *check-mate*.
 
 

Poveste şi cerinţă...

h2. Date de intrare

Fişierul de intrare $petrick.in$ va conţine $N$, numărul de piese. Următoarele $N$ linii vor conţine fiecare câte un şir de caractere din setul {*_king_*, *_rook_*, *_queen_*, *_bishop_*, *_knight_*}, un şir de caractere din setul {*_black_*, *_white_*} şi două numere întregi din multimea {$1$, $2$, $3$, $4$, $5$, $6$, $7$, $8$}, care indică poziţia piesei pe tablă. Primul şir indică tipul piesei, în timp ce al doilea indică care dintre jucătorii deţine piesa.

Fişierul de intrare $petrick.in$ ...

h2. Date de ieşire

Fişierul de ieşire $petrick.out$ trebuie să conţină un şir care descrie dacă vei câştiga în următoarea mişcare sau nu. Acest şir va fi *Checkmate!* dacă vei câştiga în următoarea mişcare sau *Bad Luck!* altfel.

În fişierul de ieşire $petrick.out$ ...

h2. Restricţii

* $1$ ≤ $N$ ≤ $16$
* Limita de timp a acestei probleme a fost micsorata de la 1 secunda la 0.01 pentru a proteja evaluatorul.

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. petrick.in |_. petrick.out |

| 4
  king white 1 1
  rook white 7 6
  queen white 4 5
  king black 8 8
| Checkmate!

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. Explicaţie

Exista cel putin o mutare care ii permite albului sa ii dea sah-mat negrului.

...

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