Play the "MOE Millions" scratch and win card and you could win up to ~$1\,000\,000~! Or you could win less than that! Or you might win nothing at all. There are ~10~ possible prizes: ~$1, $2, $5, $10, $50, $100, $1000, $10\,000, $500\,000~ and ~$1\,000\,000~.
To play, scratch off the squares on a ~3 \times 3~ grid one at a time. If you find ~3~ matching prize amounts under the scratchy stuff, you win that amount. It's that simple! Each card will contain a maximum of one set of ~3~ matching symbols. Employees of the Ministry of Education and their families are not eligible for any prizes.
OK, you've got your card, and you've scratched off ~8~ of the squares as shown on the right. What fabulous prizes could you win when you scratch off that final square?
The input will contain ~10~ test cases. Each test case will consist of nine lines representing the nine squares on the card. The first line is for the top left box, the second is for the top middle box, then top right, then middle row left, and so on down to the bottom right corner. If a box has been scratched, the line for that box will contain the prize amount that is revealed. If not, the line will contain a question mark. The cards could be in any state of play, ranging from just starting out (no boxes scratched yet) to completely finished (all boxes scratched).
Your job is to output a list of all prizes the cardholder can or will win in order from lowest to highest, separated by spaces. Each card in the input should be represented by a single line in your output. If no prize is possible, output the exact string
No Prizes Possible.
Note that the sample input below only contains one test case, but the real data files will contain ~10~ test cases, one after another, with no blank lines between. Your output should therefore consist of ~10~ lines.
$10 $100 ? $10 $1 $50 $50 $1000 $1
$1 $10 $50
Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org