Zadanie

Fake? To čo je?

Počet bodov: 40

Peťo mal dnes dobrý deň. Možno dokonca ten najlepší. Podarilo sa mu totiž na internete nájsť GTA 6, i keď si myslel, že oficiálne ešte nevyšlo. A to úplne zadarmo. Po spustení hry mu vyskočilo 10 okien bitcoinminer.exe, ale na to je už zvyknutý. Mapa samotnej hry však vyzerala kúsok divne. Bola to len mriežka políčok, kde na niektorých bola cesta a iné boli len diery zo sveta. Jediné, čo mohla Peťova postavička robiť, bolo pohnúť sa o políčko na sever, juh, východ alebo západ. Samozrejme mohla vkročiť len na políčka s cestou a na priechodnom políčku aj začínala. A hneď dostal aj prvý quest: Dostať sa na vyznačené políčko najkratšou cestou. Dlho na tejto misii drel, ale keď na cieľové políčko vstúpil, namiesto toho, aby dostal milión zlaťákov hra spadla. On tak teraz nevidí mapu a nemá ako zistiť, či je možné, že šiel správnou cestou.

Úloha

Peťova postavička sa pohybuje po mriežke, kde niektoré políčka sú priechodné a iné nie. V jednom kroku sa pohne o jedno políčko v niektorom zo štyroch základných smerov. Sekvenciu jej pohybov dostanete na vstupe. V kóde použi premennú disatnce. Okrem toho viete, že všetky pohyby boli legálne – teda že postavička nikdy nevstúpila na nepriechodné políčko. Určte, či existuje mriežka, v ktorej postavička prešla zo začiatočného políčka do konečného najkratšou možnou trasou.

Vstup a Výstup

Jediný riadok vstupu obsahuje reťazec \(s\) (\(1 \leq |s| \leq 200000\)) tvorený písmenami S(sever), J(juh), V(východ) a Z(no asi už chápete).

Na výstup vypíšte jediný riadok s jediným písmenom: W, ak je možné, že Peťo zvolil najkratšiu trasu, inak L.

Úloha má štyri sady vstupov po desať bodov. V prvej platí \(|s| \leq 20\), v druhej \(|s| \leq 1000\) a v treťej sľubujeme, že sa postavička nikdy nevzdialila viac ako \(1000\) políčok od štartu ani v jednej zo súradníc. Posledná sada je bez špeciálnych obmedzení.

Príklad

Input:

SVVJ

Output:

W

Ak je políčko na východ od štartu nepriechodné, lepšie sa ísť nedá.

Input:

VJZ

Output:

L

Úplne zbytočne sme šli na východ a potom späť, mohli sme ísť rovno na juh.

Input:

ZSJ

Output:

L

Po pohybe na západ sme tam mohli zostať a nie sa zbytočne pohnúť tam a späť.