Državno natjecanje iz informatike 2019. / Prva podskupina (1. i 2. razred) - 1. zadatak

Nakon što je proslavio Međunarodni dan mrava i mravlje kiseline, jedan mrav zaputio se na svoj najdraži štap.

Štap je dug M centimetara, a mrvice hrane za mrava nalaze se na N mjesta na štapu, i to na udaljenostima H1, H2, …, HN centimetara od lijevog kraja štapa (“H” kao “hrana”).

Prvoga dana mrav svoje putovanje započinje na nekoj udaljenosti D1 centimetara od lijevog kraja štapa, okreće se lijevo ili desno, putuje do prve mrvice na koju naiđe, jede tu mrvicu, okreće se i ide u suprotnom smjeru do prve nove mrvice na koju naiđe, jede tu mrvicu, ponovno mijenja smjer i tako dalje – jedući svaku mrvicu na koju naiđe i pritom mijenjajući smjer sve dok ne dođe do lijevog ili desnog kraja štapa.

U tom trenutku mrav odlazi sa štapa, ostavljajući preostale mrvice za buduće dane.

Idućeg dana mrav se ponovno penje na štap, započinje putovanje na nekoj novoj udaljenosti D2 od lijevog kraja štapa, okreće se lijevo ili desno i ponavlja gore opisani postupak.

I tako svakog dana, ukupno K dana. Moguće je da u nekom danu mrav dođe do kraja štapa bez nailaženja na mrvicu.

Napišite program koji simulira putovanja ovoga mrava, točnije, za svaku mrvicu ispisuje u kojemu je danu pojedena.

Ulazni podaci

U prvom su retku prirodni brojevi M (3 ≤ M ≤ 1 000 000 000), duljina štapa, N (1 ≤ N ≤ 300 000), broj mrvica, i K (1 ≤ K ≤ N), broj dana.

U drugom je retku strogo rastući niz N prirodnih brojeva H1, H2, …, HN (0 < Hi < M), udaljenosti mrvica hrane od početka štapa.

U svakom od sljedećih K redaka nalaze se prirodan broj Dk (0 < Dk < M) i znak “L” (lijevo) ili “R” (desno), početna udaljenost i početni smjer kretanja mrava u k-tom danu. Broj Dk neće biti jednak nijednom od brojeva Hi (mrav neće započeti putovanje na mrvici).

Izlazni podaci

U jedini redak ispišite N razmakom odvojenih brojeva, od kojih i-ti broj odgovara rednom broju dana u kojem je pojedena mrvica na udaljenosti Hi, ili broju 0 ako mrvica nije pojedena.

Primjer zadatka

Ulaz

10 7 3
1 3 4 5 6 7 9
8 R
8 L
2 R

Izlaz

3 3 3 0 2 1 1

Ulaz

20 10 5
2 4 6 8 10 13 14 16 18 19
17 L
1 L
3 L
9 L
17 L

Izlaz

3 3 4 4 4 1 1 1 1 1