Županijsko natjecanje 2011. godine za 1. i 2. razred Srednje Škole - 3. zadatak

Tajna špijunska agencija „K.A.U.C.H.“ u svom skrivenom laboratoriju razvija novog špijunskog robota. Za sada su razvili samo prototip tog robota, te su mu dali kodno ime Nikola.

Od svih planiranih naprednih funkcija, robot Nikola ima implementirano samo napredno izbjegavanje prepreka. Algoritam za izbjegavanje prepreka osmislila je Lucija – glavna inženjerka agencije „K.A.U.C.H.“.

U agenciji trenutno traju pripreme za opširna i intenzivna testiranja najnovije verzije robota Nikola. Testirat de se kretanje robota, pa su inženjeri na dio poda u svojoj radionici ucrtali koordinatni sustav s označenim kvadratnim poljima od po jedan metar. Uz to su niskim zidovima ogradili jedan pravokutni dio u kojem de se roboti kretati. Zidovi su paralelni s koordinatnim osima, ishodište koordinatnog sustava nalazi se u donjem lijevom uglu pravokutnog dijela, a raspored osi je kao u kartezijevom koordinatnom sustavu.

Nikola se krede u jednom od osam smjerova (paralelno s osima ili dijagonalno) brzinom od jednog polja u sekundi, a smjer kretanja mu zadaje Lucija na početku testa. Dakle, robot se iz trenutnog polja može pomaknuti u jedno od osam susjednih polja (ovisno o zadanom smjeru).

Algoritam izbjegavanja prepreka (u ovom slučaju zidova) radi na način da Nikola u svakom trenutku zna gdje se mora pomaknuti. Ukoliko bi neki pomak izazvao sudar sa zidom, Nikola prvo promjeni smjer, pa tek onda izvrši pomak.

Nikola mijenja smjer na sljededi način:

• Ako de pod kutom udariti u zid, tada de promijeniti smjer za 90°
• Ako de okomito udariti u zid, promijenit de smjer za 180°

• Ako de u jednom od dijagonalnih smjerova udariti u kut, promijenit de smjer za 180°

  

S obzirom da je ova faza testiranja iznimno važna, Lucija želi biti sigurna da su testovi točni. Odredila je Nikolinu početnu točku i smjer kretanja. Lucija de unijeti niz nasumično odabranih vremena za koje želi znati gdje se točno nalazi Nikola. Vremena ne moraju biti posložena po redu.

Vaš zadatak je napisati program koji de odgovoriti na Lucijina pitanja.

ULAZNI PODACI

U prvom retku se nalaze dva prirodna broja V i S ( 2 ≤ V,S ≤ 500 ) koji predstavljaju visinu i širinu pravokutnog područja u kojem se Nikola krede.

U drugom retku se nalaze dva broja i jedna riječ odvojeni razmacima. Brojevi X i Y predstavljaju koordinate Nikoline početne pozicije, unutar zadanog područja, a riječ se sastoji od dva velika slova engleske abecede i označava početni smjer kretanja robota.

Riječ se sastoji od dva velika slova engleske abecede, a sigurno de biti jedna od osam sljededih:

• „UU“ gore
• „DD“ dolje
• „RU“ gore desno
• „LD“ dolje lijevo
• „RR“ desno
• „LL“ lijevo
• „RD“ dolje desno
• „LU“ gore lijevo
• U trećem retku se nalazi jedan prirodni broj N ( 1 ≤ N ≤ 100 000 ) koji označava broj Lucijinih upita.

U sljedećem, četvrtom retku nalazi N prirodnih brojeva Ti ( 1 ≤ T ≤ 26 483 109 ) odvojenih razmakom, od kojih svaki predstavlja Lucijin upit za Nikolinu poziciju u vremenu Ti .

NAPOMENA: u 30% test podataka upiti de biti za vremena manja od 1000, a dimenzije pravokutnog područja de biti manje 50.

IZLAZNI PODACI

U svaki od prvih N redaka ispišite po dva broja Xi i Yi koji predstavljaju odgovor na i-to Lucijino pitanje, odnosno predstavljaju Nikolinu poziciju u trenutku Ti .

PRIMJERI TEST PODATAKA

ulaz

4 8
4 2 RR
3
4 10 12

izlaz

8 2
2 2
2 2

ulaz

3 5
3 2 RU
3
3 5 7

izlaz

4 1
2 3
2 1

ulaz

8 8
7 4 RD
4
2 6 9 11

izlaz

7 2
3 4
2 7
4 7