8. Escargot

Niet času na vysvetlenie. Musíte hneď TERAZ zjesť slimáka. Ak to nedokážete, tak sa asi stane niečo zlé. Neviem, som len zadanie úlohy číslo 8 v KSP, aj tak ma nikto nečíta.

Samozrejme, nie sme barbari. Slimák sa servíruje ako escargot, čo po Francúzsky niečo znamená.

Slimáka si vieme predstaviť ako dvojicu disjunktných útvarov (nie nutne súvislých!) pozostávajúcich z políčok v nekonečnej štvorčekovej mriežke¹, teda každý obsahuje aspoň jedno políčko a žiadne políčko sa nenachádza v oboch z nich. Jeden z týchto útvarov predstavuje svalnatú nohu slimáka, a druhý jeho ulitu. Samozrejme, ulitu jesť nechceme, pretože máme vkus a česť². Takže najprv musíme ulitu od svalnatej nohy oddeliť.

Na to existuje špeciálny exkluzívny escargot príbor, ktorým dokážeme presunúť buď celú ulitu, alebo celú svalnatú nohu o jedno políčko v jednom zo štyroch kardinálnych smerov (všetky políčka jedného z útvarov sa posunú o jedno políčko hore, dole, doprava alebo doľava). Samozrejme, v žiadnom momente sa nesmie na tom istom mieste nachádzať políčko svalnatej nohy aj ulity zároveň, pretože by nastalo verejné pobúrenie, pokles populácie potočákov, a v neposlednej rade aj kolaps Pauliho kvantových princípov a s nimi reality ako ju poznáme.

Samozrejme, vašou úlohou je zistiť, či je možné takýmito manévrami ulitu od svalnatej nohy oddeliť, a ak áno, ako. Konkrétne, treba umiestniť oba útvary do takej polohy, že v aspoň jednom zo štyroch kardinálnych smerov bude mať každé políčko jedného z nich vyššiu súradnicu ako každé políčko druhého (inak povedané bude existovať priamka rovnobežná s horizontálnou alebo vertikálnou osou, ktorá tieto útvary od seba oddeľuje).

Reklamná vsuvka

Hej. Hej! Pst! Ty! Počúvaj. Teraz ti prezradím prastaré kozmické tajomstvo. Tvoj program pravdepodobne beží príliš pomaly, pretože slimačí sliz ti zalepil procesory a grafiky. Ak chceš bežať rýchlejšie, budeš potrebovať legendárny algoritmus na násobenie polynómov menom Fast Fourier Transform³. Klikni SEM a obdrž doživotnú zásobu.

Úloha

Zistite, či je možné od seba dva útvary v nekonečnej štvorečkovej mriežke oddeliť (teda umiestniť ich tak, aby existovala priamka rovnobežná s vodorovnou alebo zvislou osou taká, že oba útvary úplne oddeľuje) iba pohybmi o jedno políčko v kardinálnych smeroch, a ak áno, zistite ako. Vaše riešenie musí pozostávať z najviac \(10^7\) pohybov. To, že takéto riešenie existuje, je garantované.

Táto úloha sa môže testovať dlho, buďte trpezliví a milí k testovaču. Zároveň si buďte vedomí, že táto úloha má jedinú sadu a nedajú sa získať čiastkové body, teda nemá zmysel odovzdávať pomalé riešenie hrubou silou.

Formát vstupu

V prvom riadku vstupu sú čísla \(m,n\), udávajúce veľkosť oblasti mriežky, ktorá obsahuje oba útvary.

Na každom z \(m\) nasledujúcich riadkov je reťazec \(n\) znakov určujúci do ktorého útvaru dané políčko riadku patrí: . ak nepatrí do ani jedného, zatiaľ čo @ a # reprezentujú oba útvary.

V jedinej sade vstupov platí \(1 \leq m,n \leq 1000\).

Formát výstupu

Ak sa útvary nedajú oddeliť vypíšte na jediný riadok výstupu číslo -1.

Ak sa oddeliť dajú, vypíšte na prvý riadok výstupu počet pohybov \(k \leq 10^7\), ktorými to dosiahnete (nemusí byť optimálny). Na nasledujúcich \(k\) riadkoch vypíšte vaše kroky vo formáte c d, kde c je znak @ alebo #, podľa toho, ktorým útvarom hýbete, a d je veľké písmenko N, E, S alebo W, podľa kardinálneho smeru v ktorom množinou hýbete v angličtine (North je hore, South je dole, East je doprava, West je doľava).

Príklady

Input:

6 4
.#..
...#
#@#.
##..
#...
.@..

Output:

5
@ N
@ E
# S
@ E
@ E

Po vykonaní týchto pohybov sa každé políčko @ nachádza napravo od každého políčka #.

Input:

4 4
##..
@...
#@.#
..##

Output:

-1