blockout

Blockout este versiunea in 3 dimensiuni a jocului tetris. Astfel, piese avand forme diferite trebuiesc plasate intr-un paralelipiped de o anumita inaltime.

In aceasta problema, va trebui sa simulati o varianta simplificata a acestui joc.

Consideram un paralelipiped cu baza de dimensiuni NxN si inaltime infinita. In interiorul acestuia, cad succesiv piese ce se vor aseza pe pozitia cea mai

joasa posibila. Piesa inainteaza pe axa verticala cate o unitate si se opreste atunci cand, fie a atins baza paralelipipedului (inaltime 0), fie se sprijina pe o piesa precedenta.

Piesele considerate vor avea deasemenea forma paralelipipedica iar pozitia lor in planul orizontal va fi data.

Cerinta

Pentru fiecare piesa se cere sa afisati inaltimea finala la care se va opri baza piesei.

Date de intrare

Prima linie a fisierului blockout.in va contine doua numere intregi N si M separate printr-un singur spatiu. N reprezinta dimensiunea bazei paralelipipedului iar M numarul de piese. Urmatoarele M linii vor contine cate 5 intregi ce corespund unei piese:

x1 y1 x2 y2 h

primii doi reprezinta coordonatele coltului stanga-sus al bazei piesei, urmatorii doi coordonatele coltului dreapta-jos al bazei piesei, si ultimul reprezinta inaltimea piesei.

Date de iesire

Pentru fiecare piesa se va scrie pe o linie in fisierul blockout.out inaltimea finala a bazei piesei.

Restrictii

1 <=N <=100

1 <=M <=15000

0 <=x1, y1, x2, y2 <=N-1

1 <=h <=100

Exemplu

blockout.in	blockout.out
10 3 1 1 2 2 1 4 5 4 5 7 0 0 9 9 10	0 0 7

Timp maxim de executie/test: 1 secunda

Batog Bogdan
UPB
bbbb@ss.pub.ro