Táto úloha je programátorská. Ako svoje riešenie odovzdaj program vo svojom obľúbenom jazyku a automaticky sa dozvieš, koľko si dostal(a) bodov. Ak si takýto typ úloh ešte nikdy neriešil(a), skús sa pozrieť ako by mal vyzerať ideálny program. Ak zatiaľ programovať nevieš, ale chcel(a) by si sa naučiť, môžeš skúsiť našu KSP School.

Keď už máme všetky balíky pozbierané na jednom mieste, môžeme ich doviezť do skladu. Ale kam ich uložíme? Sklad je veľmi veľký a police v ňom sú vysoké, takže vidíme vždy iba priamo vedľa seba a pred seba. Každý balík má svoje miesto, na ktoré sa perfektne hodí. Je to tak jednoznačné, že keď k tomu miestu prídeme, okamžite budeme vedieť, že sme na správnom mieste.

Úloha

Nájdite čo najkratšiu cestu z miesta, kde ste začali, do miesta, na ktoré sa váš balík perfektne hodí. Začínate na pozícii $(S_r, S_c)$, môžete sa otočiť doľava alebo doprava alebo urobiť krok dopredu. Vždy viete, čo je vľavo, pred vami a vpravo od vás.
Miesto na ktoré sa váš balík hodí je označené znakom X a jeho polohu dopredu neviete.

Sklad je obdĺžniková mriežka s $R$ riadkami a $C$ stĺpcami, kde každé políčko je buď prechodné (označené .), obsadené policou (označené #) alebo cieľ (označené X). Vašou úlohou je dostať sa na cieľové políčko.

Formát vstupu

Na začiatku dostanete na prvom riadku čísla $R$ a $C$ (počty riadkov a stĺpcov skladu). a v druhom riadku čísla $S_r$ a $S_c$ (pozícia štartu). Vždy začínate smerujúc na spodok.

Všetky ďalšie riadky obsahujú tri znaky oddelené medzerou, popisujúce aké políčko je vľavo, pred a vpravo od aktuálnej pozície (v tomto poradí). Políčka mimo skladu sú označované rovnako ako políčka obsadené policou. Tieto informácie dostanete na začiatku a vždy po vykonaní kroku alebo otočenia.

Pozor: po tom, čo stúpite na miesto X, už ďalší vstup nedostanete (lebo ste už hotoví). Ak sa pokúsite aj tak čítať vstup, tak vám program vyhodí chybu.

V sadách 1 a 3 môžete navyše predpokladať, že voľné políčka v sklade netvoria žiadne cykly. V sadách 2 a 4 sa cykly môžu vyskytnúť.

Formát výstupu

Na výstup vypísujte akcie, ktoré chcete urobiť (L - otočiť sa doľava, P - otočiť sa doprava, K - krok dopredu). Každú akciu vypíšte na samostatný riadok. Po každej akcii dostanete nové informácie o vašom okolí.

Aby testovanie fungovalo ako má, je nutné po vypísaní každého riadku flushnúť výstup, aby ho testovač uvidel. V C++ by malo stačiť cout << nieco << endl;, ale môžete explicitne použiť príkaz cout.flush();. V Pythone vypisujte príkazom print(cislo, flush=True) alebo po vypísaní zavolajte sys.stdout.flush(). Pre iné jazyky hľadajte ekvivalent k príkazu flush.

Hodnotenie

Ak sa váš program pokúsi ísť mimo skladu alebo do políčka obsadeného policou, bude ukončený so stavom WA. Ak váš program odošle neplatnú inštrukciu, rovnako bude ukončeny s WA.

Váš program môže použiť najviac $10 \cdot F$ krokov (kde $F$ je počet voľných políčok v sklade), po viac krokoch bude testovanie ukončené s výsledkom WA. Na počte otočení nezáleží, avšak ak sa váš program bude dlhšie otáčať na jednom mieste, bude ukončený s WA.

Príklad

>>> 5 5
>>> 0 1
>>> . # .
<<< L
>>> # . #
<<< K
>>> # # .
<<< P
>>> # . .
<<< K
>>> . . #
<<< L
>>> . . .
<<< K
>>> # X #
<<< K

(>>> znamená, že ide o vstup vášho programu, <<< zas, že ide o jeho výstup. Tieto značky sú len ilustračné, na testovači sa nevyskytujú.)

V tomto prípade sa programu podarilo ísť priamo k cieľu bez zbytočných krokov. Sklad v tomto prípade vyzeral nasledovne: