III Mistrzostwa Wielkopolski w Programowaniu Zespołowym 2-3 grudnia 2005
Zadanie B. Kasa

Opis

W pewnym kraju Ameryki Północnej paniom w sklepach coraz trudniej przychodzi liczenie. Kasy, które pokazują, ile trzeba wydać, przestają wystarczać. Twoim zadaniem jest napisanie programu dla kasy sklepowej, która powie nie tylko, ile trzeba wydać, ale też na podstawie informacji o nominałach banknotów w kasie powie, ile i jakich nominałów trzeba wydać.

Na początek jednak, jak to zwykle bywa w tym kraju, zostaną przeprowadzone odpowiednie „badania rynku”. Do testowania został wybrany sklep o wszystko mówiącej nazwie „Wszystko za 5$”. Wszystkie produkty są w tej samej cenie i kosztują 5$, a ponadto klient może naraz kupić tylko jeden taki produkt. Innymi słowy, w kasie każdy klient płaci zawsze 5$. Na początku dnia pani obsługująca kasę przynosi ze sobą z banku 10 banknotów o nominale 5$. Klienci przynoszą ze sobą dowolne ilości pieniędzy w dowolnych dostępnych nominałach. Kasa oprócz tego, że powie pani, ile jakich banknotów wydać, musi też ocenić, czy klient przypadkiem nie ma za mało pieniędzy, aby dokonać zakupu. Jeżeli klient chce zapłacić banknotami, z których nie można mu wydać reszty, także odchodzi z niczym, zabierając ze sobą swoje pieniądze. Gdy któryś z tych przypadków zajdzie, kasa oczywiście powinna poinformować o tym panią sprzedawczynię. Jeśli klient może dokonać zakupu, kasa powinna wydawać mu zawsze jak najwięcej możliwych jak największych nominałów, aby w przyszłości było jak najwięcej możliwości wydawania pieniędzy. Ważne przy tym jest, że pani zgarnia do kasy wszystkie nominały, które daje jej klient i dopiero wtedy wybiera z kasy banknoty, którymi wyda resztę (czyli kupiec może nieświadomie wymienić swoje „drobniaki” na „duże banknoty”).

Dostępne w tym kraju nominały banknotów to kolejno: 1$, 5$, 10$, 20$, 50$ i 100$. Inne, nawet jeśli występują, są tak rzadkie, że system w wersji testowej w ogóle nie ma rozpatrywać ich istnienia.

Specyfikacja wejścia

Pierwsza linia wejścia zawiera liczbę całkowitą D (1 ≤ D ≤ 50), oznaczającą liczbę zestawów danych. Pierwsza linia każdego zestawu zawiera jedną liczbę całkowitą N (0 ≤ N ≤ 100000), oznaczają liczbę klientów, którzy danego dnia przyszli do sklepu. W kolejnych N liniach znajduje się sześć liczb całkowitych abcdef (0 ≤ a,b,c,d,e,f ≤ 10) oznaczających odpowiednio liczbę nominałów 1$, 5$, 10$, 20$, 50$ i 100$ przyniesionych przez kolejnego z klientów. Kolejność opisów klientów na wejściu jest zgodna z ich kolejnością płacenia przy kasie.

Specyfikacja wyjścia

Dla każdego zestawu danych należy wypisać dla każdego z klientów w osobnej linii w jakich ilościach poszczególnych nominałów trzeba wydać resztę, zapisanych w takim samym formacie jak na wejściu, czyli w postaci sześciu liczb całkowitych a, b, c, d, e, f oznaczających odpowiednio liczbę nominałów 1$, 5$, 10$, 20$, 50$ i 100$. W przypadku gdy klient dał za mało pieniędzy, aby zakupić towar za 5$ należy wypisać na wyjściu w odpowiedniej linii Za malo pieniedzy. W przypadku gdy stan nominałów w kasie uniemożliwia wydanie pieniędzy klientowi, należy wypisać na wyjściu Nie da sie wydac. Ostatnią linią każdego zestawu danych, powinien być stan kasy na koniec dnia.

Przykład

Wejście

2
6
0 0 1 0 0 0
0 0 0 0 0 3
2 0 0 0 0 0
0 1 0 0 0 0
0 4 5 3 5 3
6 0 0 0 0 0
6
0 0 0 1 0 0
0 0 0 1 0 0
0 0 0 1 0 0
0 1 0 0 0 0
0 1 0 0 0 0
0 0 0 1 1 0

Wyjście

0 1 0 0 0 0
Nie da sie wydac
Za malo pieniedzy
0 0 0 0 0 0
0 1 6 3 5 3
1 0 0 0 0 0
5 13 0 0 0 0
0 3 0 0 0 0
0 3 0 0 0 0
0 3 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 3 0 0 1 0
0 0 0 4 0 0