Problem F
Ispusslet

Olle hatar kryss. De påminner honom för mycket om att få Wrong Answer på programmeringsproblem. När han anlände till Vallhamra Ishall och såg att det fanns $K$ ($2 \leq K \leq 20000$) stycken kryss utplacerade över isen blev han därför argare än en tjur.

Som den problemlösare han är har Olle kommit på en plan för att lösa denna katastrofala situation. Han tänker nämligen göra om alla kryss till cirklar. Isrinken kan representeras som ett $N \times M$ stort rutnät, där $K$ stycken rutor har ett kryss och de resterande $N \cdot M - K$ rutor är tomma. Rutnätets rader är numrerade från $0$ till $N-1$ uppifrån och ned, och kolumnerna är numrerade från $0$ till $M-1$ från vänster till höger. När Olle är färdig ska alla rutor som från början hade kryss i sig innehålla cirklar istället.

Till en början befinner han sig på rutan markerad med S. Denna rutan innehåller också ett kryss. I ett drag kan han börja åka i en av riktningarna uppåt, nedåt, höger eller vänster utan möjlighet att svänga. Han kommer fortsätta åka i samma riktning tills dess att han hamnar vid ett kryss eller cirkel och stannar på den rutan. Om det inte finns några kryss eller cirklar i riktningen som Olle åker i kommer han att krocka med väggen, och utsättas för en skada såpass allvarlig att han kommer tvingas avbryta sin plan. Varje gång han kommer till ett kryss stannar han helt och byter det från ett kryss till en cirkel. Om han någonsin kommer fram till en cirkel stannar han också helt och gör om det till ett kryss i sin blinda ilska. Eftersom han inte har hela dagen på sig vill han hitta en sekvens av drag som innehåller som mest $10^5$ drag och gör om alla kryss till cirklar. För lite stilpoäng vill han också sluta på samma ruta som han började, men detta är inte nödvändigt i alla testfallsgrupper.

Indata

Den första raden i indatan innehåller de tre heltalen $N,M$ och $R$ ($2 \le N \cdot M \leq 10^6$, $R \in \{ 0,1\} $). Talen $N$ och $M$ är antalet rader och antalet kolumner som rutnätet utgörs av, och $R$ berättar om du måste återvända till startrutan eller inte. Om $R = 1$ så måste du återvänta till starten, och om $R = 0$ kan du avsluta sekvensen av drag på vilken ruta som helst.

De följande $N$ raderna innehåller vardera en sträng av längd $M$, där den $i$:te av dessa ($i = 0, 1, \dots , N-1$) beskriver hur den $i$:te raden av isrinken ser ut. Varje tecken är antingen “.”, “S” eller “X”. Det är garanterat att exakt en ruta innehåller “S”, och att antalet “X” är $K - 1$ (eftersom startutan också är ett kryss).

Utdata

Om det finns en sekvens drag som gör om alla kryss till cirklar, skriv först ut längden på denna. Längden får vara som mest $10^5$. Skriv sedan ut sekvensen på nästa rad. Denna ska bestå av karaktärerna v, <, ^ och >. v betyder att Olle ska åka nedåt, ^ uppåt, < åt vänster och > åt höger. Om $R=1$ måste dessutom Olle sluta på samma ruta som han startade.

Om det inte finns en giltig sekvens av drag, skriv ut $-1$ och inget mer. Notera att huruvida en giltig sekvens existerar eller inte kan bero på om $R=0$ eller $R=1$.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Exempelfall 1

Till en början befinner sig Olle på krysset högst uppe till vänster, och rutnätet ser ut så här:

  X.X
  ...
  X.X

Efter dragen >, v och ^ befinner sig Olle högst uppe till höger och rutnätet ser ut så här:

  X.X
  ...
  X.O

Efter att han utfört dragen < och > befinner han sig fortfarande högst uppe till höger och rutnätet ser ut så här:

  O.O
  ...
  X.O

Han kommer därefter utföra dragen <, v, ^ för att skapa en kryssfri isrink, där han dessutom slutar på startpositionen (detta är dock inte ett krav på detta testfall eftersom $R=0$):

  O.O
  ...
  O.O

3 3 0
S.X
...
X.X

8
>v^<><v^

2 2 0
S.
.X

-1

2 2 0
SX
X.

3
><v

2 2 1
SX
X.

-1