Piramida

Arheologinja dr. Marina istražuje drevnu piramidu koja je nedavno otkrivena u Egiptu. Unutar piramide pronašla je skriveni zid s nevjerojatnom matricom brojeva koju su graditelji ostavili iza sebe. Dr. Marina vjeruje da su ti brojevi ključ za otkrivanje tajne skrivenog blaga u piramidi. Zid s matricom ima poseban mehanizam koji se sastoji od N redaka i M stupaca. Uz zid su nađeni zapisi s ukupno Q operacija koje su izvedene na matrici kako bi je šifrirali. Operacije su oblika "1 x" ili "2 x", gdje 1 označava da se operacija odnosi na retke, a 2 na stupce. Operacija uzme prvih x redaka/stupaca i preseli ih na kraj. Na kraju zapisa nalazi se završna matrica nakon izvođenja svih operacija. Kako bi otkrila tajnu skrivenog blaga, dr. Marina treba rekonstruirati početnu matricu prije nego što su primijenjene operacije. Možete li joj pomoći rekonstruirati matricu?

Ulazni podatci

Prvi redak sadrži dva cijela broja N i M , broj redaka i stupaca matrice. Drugi redak sadrži cijeli broj Q, broj operacija koje su izvedene na matrici. Sljedećih Q redaka sadrži po dva cijela broja oi i xi (1 ≤ oi ≤ 2, 1 ≤ xi ≤ N ako oi = 1 ili 1 ≤ xi ≤ M ako oi = 2), gdje oi označava vrstu operacije (1 za retke, 2 za stupce), a xi označava broj redaka ili stupaca koji treba premjestiti. Sljedećih N redaka sadrži po M prirodnih brojeva manjih od milijardu koji predstavljaju završnu matricu.

Izlazni podatci

Ispišite N redaka s po M brojeva koji predstavljaju početnu matricu prije izvođenja operacija.

Bodovanje

Podzadatak Bodovi Ograničenja

1 6 1 ≤ N, M ≤ 30, 1 ≤ Q ≤ 30 2 13 1 ≤ N, M ≤ 1000, 1 ≤ Q ≤ 1000 3 21 1 ≤ N, M ≤ 2000, 1 ≤ Q ≤ 5 ∗ 105

Probni primjeri

ulaz ulaz ulaz 3 3 3 3 3 4 1 1 2 1 2 2 2 1 3 1 2 3 1 2 3 2 1 4 5 6 4 5 6 2 1 4 3 7 8 9 7 8 9 5 8 7 9 6 10 11 12 izlaz izlaz izlaz 4 5 6 2 3 1 7 8 9 5 6 4 3 2 1 4 1 2 3 8 9 7 9 5 8 7 12 6 10 11