SVK-B - Klávesnica

Väčšina (všetky?) virtuálne klávesnice sa snažia napodobniť rozloženie kláves reálnej klávesnice. Na virtuálnej klávesnici existuje veľa možností ako emulovať stlačenie klávesu. Ak máme k dispozícii myšku, jednoducho klikneme na virtuálny kláves. Zaujímavejšie je písanie na virtuálnej klávesnici ovládanej gamepadom alebo navigačnými šípkami na diaľkovom ovladaní. V tomto prípade je na virtuálnej klávesnici zobrazený kurzor označujúci vybraný kláves (písmeno). Navigačnými šípkami (nahor, nadol, vľavo, vpravo) vieme tento kurzor presúvať na susedné klávesy. Keď ho presunieme na želaný kláves stlačením tlačidla OK potvrdíme výber klávesu a písmeno prislúchajúce tomuto klávesu sa napíše. Ak je kurzor na písmene Q a chceme napísať písmeno M, znamená dosť veľa stlačení navigačných šípok na to, aby sme kurzor presunuli na kláves s písmenom M. A teraz si predstavte, že chcete napísať text MQMQMQMQ. Nepomohlo by, keby sa písmená boli na viacerých klávesoch? Preskúmajme to!

Uvažujme virtuálnu klávesnicu vo forme (dvojrozmernej) tabuľky. Každá bunka tabuľky predstavuje jeden kláves s nejakým písmenom. Kurzor vieme presúvať (meniť vybraný kláves) pomocou tlačidiel navigačných šípok - nahor, nadol, vľavo a vpravo. Ak sa kurzor nachádza na okraji tabuľky, stlačenie tlačidla navigačnej šípky, ktoré by spôsobilo presun kurzora za okraj tabuľky, sa ignoruje (napr. ak je kurzor na najvyššom riadku, stlačenie šípky nahor kurzor nepresúva). Stlačením tlačidla OK vypíšeme písmeno klávesu, na ktorom sa práve nachádza kurzor. Ak sa písmeno v tabuľke nachádza viackrát, je jasné, že existuje viacero spôsobov ako napísať nejaké slovo. Ak chceme toto slovo napísať čo najrýchlejšie, prirodzene nás zaujíma taký spôsob napísania slova, v ktorom stlačíme čo najmenej tlačidiel.

Úloha

Vytvorte program, ktorý pre zadané rozloženie písmen na virtuálnej (tabuľkovej) klávesnici a zadané slovo vypočíta najmenší možný počet stlačení tlačidiel (nahor, nadol, vľavo, vpravo, OK), ktoré potrebujeme na napísanie slova.

Vstup

Prvý riadok vstupu obsahuje tri čísla R (1 ≤ R ≤ 50), S (1 ≤ S ≤ 50) a n (1 ≤ N ≤ 50). Číslo R určuje počet riadkov tabuľky klávesnice, S počet stĺpcov tabuľky klávesnice a N počet slov, ktoré chceme analyzovať. V nasledujúcich R riadkoch je v každom riadku S veľkých písmen anglickej abecedy (A-Z), ktoré v poradí zľava definujú písmená na jednotlivých klávesoch v tomto riadku virtuálnej klávesnice. Po týchto riadkoch nasleduje N riadkov popísujúcich jednotlivé analyzované slová. Každý riadok sa skladá z 2 čísel r (0 ≤ r < R) a s (0 ≤ s < S), a reťazca z veľkých písmen anglickej abecedy dĺžky aspoň 1 a nanajvýš 50. Čísla r a s určujú riadok a stĺpec (indexujúc od 0) klávesu, na ktorom sa iniciálne nachádza kurzor.

Môžete predpokladať, že každé písmeno anglickej abecedy sa nachádza na klávesnici aspoň raz, t.j. akékoľvek zadané slovo je možné na klávesnici napísať.

Výstup

Výstupom je N riadkov, pričom i-ty riadok obsahuje minimálny počet stlačení tlačidiel potrebných na napísanie i-teho slova s ohľadom na definovanú iniciálnu pozíciu kurzora.

Príklad

Vstup:

5 12 6
OMAYJGPQHRKO
PRKUJFJHUBQP
NHLQUXUSIAFV
MDZHVWSTNACR
YGIMPALDXEIA
1 7 PROGRAMATORSKA
1 5 SUTAZ
0 1 STUDENTSKA
0 2 VEDECKA
2 3 KONFERENCIA
0 6 PFUPJS

Výstup:

64
18
37
30
43
15