sponsori

Intr-un oras din Romania, primarul s-a hotarat sa nu mai astepte integrarea in UE si vrea sa reconstruiasca singur cele N scoli pe care le are in administratie.

Consilierii primarului au reusit sa convinga M sponsori sa doneze o anumita suma fiecarei scoli pentru renovare. Sa notam cu s_i,j lei suma donata de sponsorul i scolii j. Datorita noii reforme monetare sumele donate nu sunt numere intregi ci au exact 4 zecimale. Primarul a constatat ca suma totala primita de o scoala si suma totala donata de un sponsor sunt numere intregi de lei. Pentru ca nu vrea sa se complice, primarul vrea sa convinga sponsorii sa modifice sumele donate fiecarei scoli astfel incat fiecare suma donata sa fie un numar intreg de lei.

Totusi el trebuie sa tina cont de urmatoarele restrictii:

suma totala primita de fiecare scoala sa nu se modifice
suma totala donata de fiecare sponsor sa nu se modifice
pentru fiecare scoala, valoarea absoluta a diferentei dintre suma propusa de fiecare sponsor si suma propusa de primar sa fie strict mai mica de 1 leu

Cerinta

Dandu-se numarul de scoli, numarul de sponsori si suma donata de fiecare sponsor fiecarei scoli, ajutati-l pe primar sa propuna noi sume care sa respecte conditiile de mai sus.

Date de intrare

Fisierul de intrare sponsori.in va contine:

Pe linia 1: doua numere intregi N, M reprezentand numarul de scoli si numarul de sponsori
Pe liniile 2..M+1: cate N numere reale, al j-lea numar pe linia i+1 reprezentand suma donata de sponsorul i pentru scoala j

Date de iesire

Fisierul de iesire sponsori.out va contine pe liniile 1..M cate N numere intregi, al j-lea numar pe linia i reprezentand suma propusa de primar ca sponsorul i sa o doneaze scolii j. Sumele vor fi afisate fara zecimale.

Restrictii si precizari

Numere reale din input vor fi date cu exact 4 zecimale
1 <= N, M <= 100
0 <= s_i,j <= 2000
Daca exista mai multe solutii se va afisa oricare dintre ele.

Exemplu

sponsori.in	sponsori.out	Explicatie
2 2 1.2500 3.7500 2.7500 1.2500	1 4 3 1	Primul sponsor va dona 1 leu in loc de 1.2500 lei primei scoli si 4 lei in loc de 3.7500 lei celei de-a doua scoli. Suma totala donata de el va ramane 5 lei. Al doilea sponsor va dona 3 lei in loc de 2.7500 lei primei scoli si 1 leu in loc de 1.2500 lei celei de-a doua scoli. Suma totala donata de el va ramane 4 lei. Sumele totale primite de scoli, 4 respectiv 5 lei, raman neschimbate.

Timp de executie: 0.4 secunde/test.

Alexandru Mosoi
http://mosoi.lumina.ro
Universitatea Politehnica Bucuresti
Contact: alexandru.mosoi # gmail.com