4. Turnaj Veľkých Šachistov

V Slovakistane sa pred rokom rozhodli osadníci usporiadať národný šachový turnaj. Za prvé miesto sa dal získať diplom, a tak všetci hrali ako o život. Keďže sa však nehralo na čas, vyskytol sa problém – hráči nechceli priznať prehru. Stále len tvrdili, že určite nemajú mat, však určite sa z tej situácie dá nejak dostať, keby len mali ešte chvíľku na rozmýšlanie… A možno ešte jednu… Osadníci si teda na pomoc zavolali šikovných programátorov, ktorí ich problém vyriešili.

Tento rok osadníci plánujú usporiadať národný šachový turnaj zas. Samozrejme, tohtoročný turnaj musí byť lepší, napínavejší, veľkolepejší – a hlavne – väčší. Preto sa tento rok nebude na turnaji hrať šach na obyčajných šachovniciach rozmerov \(8 \times 8\), ale na šachovniciach \(n \times n\), a to s \(f\) figúrkami.

S týmto je však problém – programy šikovných programátorov totiž na takýchto veľkých šachovniciach už nestíhajú rozhodnúť, či má niektorý z hráčov šach alebo mat. Osadníci Slovakistanu teda opäť potrebujú pomoc!

Úloha

Pre daný popis šachovnice rozlíšte, či má niektorý z hráčov šach alebo mat. Pritom berte do úvahy len obyčajné pohyby figúrok (komplikované ťahy ako rošáda, en passant, pohyb pešiakom o dva políčka vpred a povýšenie pešiaka sa v Slovakistane neakceptujú).

Ak má práve jeden z hráčov šach, zistite tiež, koľko má platných ťahov (po ktorom už jeho kráľ nebude ohrozený).

Formát vstupu

V prvom riadku je číslo \(1 \leq t \leq 3000\), udávajúce počet šachovníc na vstupe. Nasleduje \(t\) popisov šachovníc.

Popis šachovnice začína jedným riadkom s číslami \(2 \leq n,f \leq 100\,000\): dĺžka strany šachovnice a počet figúrok na nej. Nasleduje \(f\) riadkov, každý popisujúci jednu figúrku súradnicami políčka na ktorom stojí \(x_i\) a \(y_i\), a jej typom \(z_i\). Políčko v ľavom hornom rohu má súradnice \((1,1)\) a v pravom dolnom rohu \((n,n)\). Znak \(z_i\) je písmeno označujúce typ figúrky; Každé \(z_i\) je jedno z písmen KQRBHP, reprezentujúce v tomto poradí kráľa, kráľovnú, vežu, strelca, koňa, a pešiaka.

Bielemu hráčovi patrí horná strana šachovnice (menšie \(y_i\)) a jeho figúrky sú označené malými písmenami. Teda bieli pešiaci sa pohybujú v kladnom smere \(y_i\). Čiernemu hráčovi patrí dolná strana šachovnice a jeho figúrky sú označené veľkými písmenami. Jeho pešiaci sa pohybujú v zápornom smere \(y_i\). Za každým popisom šachovnice je jeden prázdny riadok.

Platí \(1 \leq x_i,y_i \leq n\); žiadne dve figúrky nestoja na rovnakom políčku, a na každej šachovnici je práve jeden biely kráľ k a jeden čierny kráľ K. Nakoniec môžete predpokladať, že vstupy sú rozumné, teda v každom vstupe súčet \(n,f \leq 200\,000\).

V prvej sade \(n = 8\).

Formát výstupu

Pre každú šachovnicu vypíšte jeden riadok s jednou z nasledovných hlášok:

• “Neutralna situacia.”, ak žiaden z kráľov nie je ohrozený nepriateľskou figúrkou.

• “Nemozna situacia.”, ak sú obaja králi ohrození nepriateľskou figúrkou.

• “{farba} hrac ma sach. Ma \(x\) platnych tahov.”, kde {farba} je “Biely”, resp. “Cierny”, ak je kráľ tohto hráča v ohrození, ale existuje \(x\) platných ťahov niektorými jeho figúrkami takých, po ktorom už v ohrození nebude.

• “{farba} hrac ma mat.”, kde {farba} je “Biely”, resp. “Cierny”, ak je kráľ tohto hráča v ohrození, a neexistuje platný ťah niektorou z jeho figúrok taký, po ktorom už v ohrození nebude.

Príklady

Input:

3
8 4
5 1 k
4 3 H
4 5 h
5 7 K

8 4
5 2 h
3 3 k
6 4 H
4 5 K

8 6
1 1 k
4 1 H
4 2 H
2 3 H
3 3 H
7 6 K

Output:

Nemozna situacia.
Neutralna situacia.
Biely hrac ma mat.

Input:

4
8 7
1 1 k
4 1 H
4 2 H
2 3 H
3 3 H
7 6 K
2 7 r

8 9
1 1 K
7 1 R
8 1 r
1 2 R
3 2 h
8 2 r
1 5 r
2 5 r
6 6 k

8 6
1 1 k
8 2 R
4 4 B
2 5 R
7 6 K
3 7 q

8 9
3 2 P
4 2 P
5 2 P
3 3 P
4 3 k
5 3 P
4 4 P
5 4 p
4 5 K

Output:

Biely hrac ma sach. Ma 1 platnych tahov.
Cierny hrac ma mat.
Biely hrac ma sach. Ma 1 platnych tahov.
Cierny hrac ma sach. Ma 5 platnych tahov.