Državno natjecanje 2018. / Osnovna škola (8. razred) - 3. zadatak

Na treningu malonogometnog tima „Višeslav“, N igrača posloženih u krug vježba dodavanje lopte. Kada igrač primi loptu, smije je poslati samo igračima na zadanim udaljenostima od A, B ili C igrača lijevo ili desno u krugu. Kada igrač odlukom trenera ispadne iz igre, njemu susjedni igrači tada prirodno postaju međusobni susjedi u krugu, čime se mijenjaju i udaljenosti igrača u krugu.

Trener ponekad zatraži da se lopta pošalje nekom određenom igraču u krugu. Igrači tada biraju najkraći put, tj. šalju loptu koristeći minimalan broj dodavanja lijevo ili desno za A, B ili C igrača.

Napišite program koji unosi imena igrača redom kojim su posloženi u krug i potom simulira ovu igru, obrađujući trenerove zahtjeve koji mogu biti:

• „IZBACI slovo“ -- svi igrači čije ime počinje zadanim slovom ispadaju iz kruga (ako takvih ima),
• „SALJI ime1 ime2“ -- potrebno je ispisati minimalan broj dodavanja kojim će lopta od prvog navedenog igrača (ime1) doći do drugog (ime2), ili broj -1 ako to nije moguće postići.

Napomena. Ako veličina kruga zbog izbacivanja igrača postane manja od udaljenosti dodavanja (A, B ili C), igrači i dalje broje za tu udaljenost ulijevo ili udesno od sebe, što znači da će možda brojenjem prijeći puni krug (brojeći i samoga sebe).

ULAZNI PODACI

U prvom retku nalazi se prirodan broj N (3 ≤ N ≤ 100 000), broj igrača u početnom krugu.

U sljedećem retku nalaze se prirodni brojevi A, B i C (1 ≤ A, B, C < N), udaljenosti iz teksta zadatka. (Među njima može biti jednakih, čime se broj dopuštenih udaljenosti efektivno smanjuje na jednu ili dvije.)

U sljedećih N redaka nalaze se međusobno različita imena igrača u krugu (sastavljena od 3-20 malih slova engleske abecede) navedenih u smjeru kazaljke na satu.

U sljedećem retku nalazi se prirodan broj K (1 ≤ K ≤ 100 000), broj trenerovih zahtjeva.

U svakom od sljedećih K redaka nalazi se zahtjev u jednom od dvaju oblika iz teksta zadatka.

Barem jedan zahtjev bit će tipa SALJI. Dva igrača u zahtjevu SALJI uvijek će biti međusobno različiti i prisutni u krugu. U krugu će uvijek ostati barem tri igrača.

IZLAZNI PODATCI

Za svaki zahtjev tipa SALJI u zaseban redak ispišite traženi odgovor.

PRIMJERI TEST PODATAKA

Ulaz

5
2 3 3
irena
vlado
katarina
zoran
jankec
2
SALJI zoran irena
SALJI jankec irena

Izlaz

1
2

Ulaz

4
3 3 3
marko
anica
tomislav
dragica
3
SALJI marko tomislav
IZBACI a
SALJI marko tomislav

Izlaz

2
-1

Objašnjenje

Opis prvog primjera:

Zoran -> Irena (dodavanje za B ulijevo). Jankec -> Katarina -> Irena (dva dodavanja za A ulijevo).

Opis drugog primjera:

Marko -> Dragica -> Tomislav (dva dodavanja za A udesno). Izbacujemo iz kruga Anicu. Nije moguće poslati loptu od Marka do Tomislava