mars

John Carter istražuje Mars i super se provodi; medutim, povremeno on mora stati, odmoriti se, i popiti malo marsovske kafe u nekom od kafica širom Velikog kanala. Problem je što placanje kafe na Marsu znaci placanje u lokalnoj valuti. Širom Marsa, cijene su zadate u Quaklu-ima (najmanja novcana jedinica), i Simbol za Quaklu je Q. Medutim, svaki grad proizvodi sopstvene novcice (Marsovci ne koriste papirni novac). Tipicna marsovska zajednica koristi izmedu jednog i 20 novcica razlicitih vrijednosti. Na primjer, u gradu Armstrong, postoji 5 razlicitih novcica sa simbolima X, B, G, H i T. Oni vrijede 3 Q, 24 Q, 39 Q, 119 Q i 453 Q, respektivno.<br><br>

Kao drugi primjer u gradu Burroughs, postoje tri novcica J, K i B, oni vrijede 2 Q, 4 Q i 5 Q, respektivno.<br><br>

Kombinacije novcica se pišu pocevši od novcica najvece vrijednosti prema novcicima najmanje vrijednosti. Pošto na Marsu postoje stotine zajednica sa razlicitim sistemima, nijedna zajednica ne koristi simbol Q za bilo koji novcic. (Što je sreca, jer se simbolom Q oznacava smijeh, greške, besplatna kafa, smjer kretanja, i kao skracenica za izraz: "Oprostite, ali Vaš pipak se nalazi u mom trecem oku", itd.)<br><br>

Cijena šolje marsovske kafe varira izmedu 1 Q i 15000 Q (dobra kafa je skuplja). Svaki kafic zahtijeva da posjetioci plate svoje racune tacnim iznosom novcica. (Po zakonu, svaki kafic mora postaviti svoje cijene tako da je moguce platiti kafu tacnim iznosom novcica, u suprotnom je kafa besplatna) Oni takoder žele da njihovi posjetioci plate sa što je moguce manjim brojem novcica. Kada postoje dva nacina placanja iste sume sa istim brojem novcica, preferiraju se novcici sa vecom vrijednošcu.<br><br>

Na primjer, da bi se platio racun od 51 Q u Armostrongu, jedan nacin placanja bi bio korištenjem jednog novcica G i 4 novcica X (piše se: GXXXX). Umjesto toga, taj isti iznos se placa korištenjem 2 novcica B i jednim novcicem X (piše se: BBX). U mjestu Burroughs, racun od 12 Q se placa sa dva novcica B i jednim J (piše se: BBJ) umjesto sa tri novcica K. (piše se: KKK)<br><br>

Vaš zadatak je da napišete program da pomognete John Carter-u da plati kafu na odgovarajuci nacin.<br><br>

Ulazni podaci<br>

Sa prvog reda standardnog ulaza se dva cijela broja n, m (0 < n < 21, 0 < m < 15001). Broj n predstavlja broj razlicitih novcica, a broj m predstavlja cijenu kafe u proizvoljnoj marsovskoj zajednici. Nakon toga slijedi n redova koji opisuju novcice na slijedeci nacin: Svaki red pocinje sa jednim velikim ili malim slovom engleske abecede koje predstavlja simbol za odgovarajuci novcic u toj zajednici, nakon cega slijedi pozitivna cjelobrojna vrijednost (manja od 15000) odvojena jednim simbolom razmaka (space), koja predstavlja vrijednost tog novcica.<br><br>


Izlazni podaci<br>

Na standardni izlaz potrebno je ispisati jednu liniju koja predstavlja simbole novcica kojima se placa racun na gore opisani nacin, odnosno odgovarajuci izlaz ako je kafa besplatna.<br><br>

Testni primjeri<br><br>

Ulaz<br>
5 51<br>
X 3<br>
B 24<br>
G 39<br>
H 119<br>
T 453<br>
<br>
Izlaz<br>
BBX<br>
<br>
Ulaz<br>
3 12<br>
J 2<br>
K 4<br>
B 5<br>
<br>
Izlaz<br>
BBJ<br>
<br>
Ulaz<br>
1 3<br>
F 4<br>
<br>
Izlaz<br>
Q<br>