== 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 (amintiţi-vă că sunteţi unul talentat!)._

_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*.
 

În mod formal, vi se dă o masă de şah *fără pioni*, cu piese de $N$ pe ea şi vi se cere să vedem dacă albul poate negru negru prin mutarea unei bucăţi implică mutarea a două bucăţi). Reţineţi că starea mesei de şah poate fi atinsă într-un joc ipotetic de şah, în conformitate cu regulile bine cunoscute ale şahului.

h2. Date de intrare

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

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.

h2. Date de ieşire

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

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.

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 |

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

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

|
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") ==

\ Begin {problemă} {Petrick}
{\ textsl {input standard}} {\ textele {output standard}}
{1 secunda}
{256 MB}
 
În mod formal, vi se dă o masă de şah \ textbf {fără pioni), cu piese de $ N $ ($ N \ leq 16 $) pe ea şi vi se cere să vedem dacă albul poate negru negru prin mutarea unei bucăţi implică mutarea a două bucăţi). Reţineţi că starea mesei de şah poate fi atinsă într-un joc ipotetic de şah, în conformitate cu regulile bine cunoscute ale şahului.
 
\ textit {O scurtă descriere a subsetului de şah care este relevant urmează, cu caractere cursive. Şahul este un joc jucat pe o masă pătrată de $ 8 ori 8 $, cu diferite piese. Piesele sunt fie împăraţi, regine, episcopi, cavaleri, fie călugări. Fiecare piesă poate fi negru sau alb, iar fiecare piesă se află pe o singură celulă. Nicio bucată nu împarte o celulă. Fiecare piesă poate, în funcţie de tipul său, să se deplaseze la alte celule; în special:} \\
 
\ Begin {itemize}
\ item \ textit {Regele se poate muta în orice celulă care împarte cel puţin un punct (inclusiv colţurile) cu celula sa actuală}.
\ item \ textit {Ceaşca poate să se deplaseze ortogonal în sus, în jos, în stânga sau în dreapta oricare distanţă, atâta timp cât nu "sări peste" alte piese}
\ item \ textit {Episcopul poate muta în diagonală orice distanţă, atâta timp cât nu "sări peste" alte părţi}
\ item \ textit {Regina poate realiza orice mutare pe care un vîrf sau un episcop o poate face}
\ item \ textit {Cavalerul se poate muta ortogonal în sus, în jos, în stânga sau în dreapta cu două celule, urmată imediat de o mişcare suplimentară a unei celule perpendiculare pe prima (în forma literei mari); reţineţi că cavalerul poate "sări peste" alte piese}
\ End {itemize}
 
 
\ Textit {
Există tocmai un rege al fiecărei culori \\
Există cel mult două vârfuri, episcopi şi cavaleri de fiecare culoare \\
Dacă există doi episcopi de aceeaşi culoare, atunci se garantează că un episcop nu se poate muta după ce se va muta în celula ce conţine celălalt episcop.
O piesă nu se poate muta într-o celulă care conţine o bucată de aceeaşi culoare. Dacă o piesă se mişcă într-o celulă dintr-o bucată de culoarea opusă, atunci piesa care se afla pe celulă iniţial este scoasă din joc. \\
Spunem că o culoare este în \ textit {check} dacă şi numai dacă o bucată de culoarea opusă s-ar putea muta în celula care conţine regele acelei culori. Nu este permis ca o culoare să facă o mişcare care să o facă să fie verificată. \\
Spunem că o culoare este în \ textit {check-mate} dacă şi numai dacă este sub control şi nu poate face mişcări legale. \\
Acum, este necesar să vedem dacă albul poate face o mişcare legală care pune negrul în \ textit {check-mate}
}
 
\Fişier de intrare
Intrarea va conţine $ N $, numărul de bucăţi. Următorul va urma liniile $ N $ care vor conţine fiecare câte un şir din setul {text {{{king, rook, queen, episcop, knight \}}, un şir din setul \ texttt {\ {negru, alb \}} şi două numere întregi din textul {\ {1, 2, 3, 4, 5, 6, 7, 8}}, care indică poziţia piesei pe masă. Primul şir indică tipul piesei, în timp ce al doilea indică care dintre jucătorii deţine piesa.
 
\Fisier de iesire
Rezultatul trebuie să conţină un şir care descrie dacă veţi câştiga în următoarea mişcare sau nu. Acest şir va fi \ texttt {Checkmate!} Dacă veţi câştiga în următoarea mişcare sau \ texttt {Bad Luck!} Altfel.
 
\Exemplu
 
\ Begin {example}
\ Exmpfile {example.in
4
rege alb 1 1
rook alb 7 6
regina albă 4 5
regele negru 8 8
} {Example.out
Şah-mat!
}%
\ End {exemplu}
\ End {problemă}