Državno natjecanje iz informatike 2016. / Druga podskupina (3. i 4. razred) – Drugi dan natjecanja - 2. zadatak

Mirko se bavi istraživanjem posljedica globalnog zatopljenja te u svom laboratoriju vrši eksperimente u kojima topi kocke leda laserima.

U eksperimentu je n 2 kockica leda poredanih u kvadratnu mrežu koja se sastoji od n redaka označenih brojevima od 1 do n odozgo prema dolje te n stupaca označenih brojevima od 1 do n slijeva nadesno.

Laseri su postavljeni uz lijevi odnosno gornji rub mreže te su usmjereni ravno prema svim kockicama u jednom retku odnosno stupcu. Na početku eksperimenta sve lasere istovremeno upalimo.

Kockica leda izložena laserskoj zraci se otopi nakon točno jedne sekunde.

Dokle god se kockica leda ne otopi u potpunosti, laserska zraka je blokirana te ne prodire dalje kroz redak odnosno stupac.

Vrijeme otapanja je jednako jednoj sekundi čak i ako je kockica istovremeno izložena zrakama iz dva različita lasera.

Pojedini laser se automatski gasi u trenutku kada su otopljene sve kockice u njegovom retku odnosno stupcu.

Ulazni podaci

U prvom redu nalaze se tri prirodna broja n, a i b (n ≤ 109 , a, b ≤ 105 ) – redom dimenzije mreže, broj lasera uz lijevi rub te broj lasera uz gornji rub mreže.

U drugom redu nalazi se a prirodnih brojeva r1, . . . , ra (1 ≤ r1 < r2 < . . . < ra ≤ n), gdje je rk oznaka retka k-tog po redu lasera postavljenog uz lijevi rub mreže.

U trećem redu nalazi se b prirodnih brojeva s1, . . . , sb (1 ≤ s1 < s2 < . . . < sb ≤ n), gdje je sk je oznaka stupca k-tog po redu lasera postavljenog uz gornji rub mreže.

Izlazni podaci

U prvi red ispišite a brojeva t1, . . . , ta, gdje je tk vrijeme gašenja k-tog po redu lasera postavljenog uz lijevi rub mreže.

U drugi red ispišite b brojeva u1, . . . , ub, gdje je uk vrijeme gašenja k-tog po redu lasera postavljenog uz gornji rub mreže.

Primjer zadatka

ULaz

5 4 3
1 2 4 5
1 2 5

Izlaz

3 4 4 5
2 3 5

Ulaz

8 3 2
2 3 7
5 6

Izlaz

6 6 8
7 7

Ulaz

8 2 3
1 4
5 6 8

Izlaz

5 5
8 8 8