Državno natjecanje 2016. / Osnovna škola (7. razred) - 3. zadatak

Slavko je predložio Mirku novu igru:

“Uzmimo jedan obični bijeli papir. Ja ću ga podijeliti crtama na N redaka i M stupaca i tako dobiti N x M kvadratića. U svaki kvadratić koji tako nastane upisat ću jedan broj.

Zatim ću papir nekoliko puta presaviti. Papir se presavija na sljedeći način.

Prvo se izabere jedan rub papira i jedna crta koja je paralelna s izabranim rubom.

Zatim se papir presavije pomičući izabrani rub tako da se dio papira od ruba do crte koja je odabrana preklopi preko odabrane crte i čvrsto pritisne na ostatak papira.

Na taj će se način papir smanjivati, a neki kvadratići preklopit će se s nekim drugim kvadratićima.

Kažemo da se dva kvadratića nalaze na istoj poziciji ako su se preklopili.

Nakon svih presavijanja reći ću ti da pogledaš dobiveni papir i za svaku poziciju odrediš zbroj brojeva na toj poziciji.”

Budući da Mirko ipak ne vidi kroz papir, napiši program koji će mu pomoći odgovoriti na Slavkova pitanja.

ULAZNI PODATCI

U prvom retku nalaze se prirodni brojevi N i M (1 ≤ N, M ≤ 100), broj redaka i broj stupaca iz teksta zadatka.

U svakom od idućih N redaka nalazi se M brojeva ai,j (0 ≤ ai,j ≤ 1000) koji predstavljaju brojeve koje je Mirko upisao na papir u svaki kvadratić prije savijanja.

U idućem retku nalazi se prirodan broj K (1 ≤ K ≤ N + M - 2), broj presavijanja papira.

U svakom od idućih K redaka nalazi se jedno od slova “U”, “D”, “L” ili “R” te prirodni broj.

Slovo označava koji kraj papira je Slavko izabrao prilikom presavijanja, tj. “U” - gornji rub, “D” - donji rub, “L”

lijevi rub, “R” - desni rub.

Broj označava koliko udaljenu crtu od izabranog ruba papira je Slavko izabrao. Odabrana crta nalazit će se uvijek unutar papira te ona neće biti rub papira.

IZLAZNI PODATCI

Neka su R i S broj preostalih redaka i stupaca papira nakon presavijanja.

U R redova potrebno je ispisati S brojeva odvojenih razmakom koji predstavljaju traženi zbroj iz teksta zadatka za svaku poziciju.

PRIMJERI TEST PODATAKA

Ulaz

5 5
1 0 1 0 1
0 2 0 1 0
1 1 1 1 1
1 2 3 4 5
5 4 3 2 1
3
L 1
R 3
D 2

Izlaz

1 0 2
1 3 14
6 5 9

Ulaz

1 8
1 2 1 3 21 5 6 1
4
L 2
L 5
L 1
L 2

Izlaz

25 15

Objašnjenje

Opis prvog test podatka: Traženi zbrojevi nakon svakog presavijanja: