La firma la care lucrează Gigel există M tipuri de camioane, din fiecare tip existând N exemplare. Gigel aşează camioanele firmei pe N rânduri, aşezând pe fiecare coloană numai camioane de acelaşi tip. Se formează astfel o matrice în care liniile sunt numerotate de sus în jos de la 1 la N, iar coloanele sunt numerotate de la stânga la dreapta de la 1 la M.
În fiecare noapte vine o bandă de hoţi. Şeful bandei anunţă: “în noaptea aceasta vom fura toate camioanele care se află în zona dreptunghiulară având colţul stânga-sus pe linia x1 şi coloana y1, iar colţul opus pe linia x2 şi coloana y2.
În dimineaţa următoare, Gigel vede acest lucru, şi „acoperă” furtul: pe fiecare linie în care există spaţii libere deplasează spre stânga toate camioanele care se află în dreapta locului liber rămas.
De exemplu, pentru N=3 şi M=5 iniţial avem următoarea amplasare: 1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
În prima noapte hoţii fură camioane, din dreptunghiul cu colţul stânga-sus în linia 2,coloana 2 şi colţul dreapta-jos linia 3 coloana 3. Astfel, în ziua următoare, după ce Gigel deplasează camioanele, amplasarea este următoarea: 1 2 3 4 5
1 4 5
1 4 5
Dacă în a doua noapte hoţii fură din nou din dreptunghiul cu colţul stânga-sus în linia 1, coloana 1 şi colţul dreapta-jos în linia 3, coloana 2, după deplasările făcute ziua de Gigel, amplasarea este următoarea: 3 4 5
5
5
Cerinţă
Cunoscând câte tipuri de camioane există la firmă iniţial, pe câte randuri au fost aşezate, numărul K de zile în care au loc furturi şi coordonatele dreptunghiurilor din care fură hoţii în fiecare noapte, determinaţi ce tipuri de camioane se află pe o anumită coloană din amplasarea finală.
Date de intrare
Fişierul de intrare camion.in conţine pe prima linie 4 numere naturale: N M K C, reprezentând numărul de rânduri pe care au fost aşezate camioanele, numărul de coloane, numărul de nopţi în care vor fura hoţii camioane, respectiv numărul coloanei pentru care se doreşte să se afle ce tipuri de camioane conţine la final. Pe fiecare dintre următoarele K linii se vor afla câte 4 numere naturale. Pe linia i+1 se află x1 y1 x2 y2, (x1,y1) reprezentând linia şi coloana colţului stânga-sus, iar (x2,y2) linia şi coloana colţului dreapta-jos al dreptunghiului din care fură hoţii în noaptea i. Numerele situate pe aceeaşi linie sunt separate prin câte un spaţiu.
Date de ieşire
Fişierul de ieşire camion.out va conţine N linii, pe fiecare câte un număr întreg. Numărul de pe linia i va reprezenta tipul camionului de pe linia i şi coloana C, după K zile. În caz că pe linia i nu se găseşte nici un camion, se va afişa valoarea 0 pe linia respectivă.
Restricţii
1 <= N <= 600
1 <= C <= M <= 600
0 <= K <= 30000
Nu este obligatoriu ca dreptunghiul din care se va efectua un furt să conţină camioane în fiecare loc.