import java.util.Scanner;
import java.util.ArrayList;
import java.io.File;

public class Problem_1 {
    public static void main(String[] args) {
        try {
            Scanner file = new Scanner(new File("C:\\Users\\Mike\\Desktop\\problem_1_scratch_and_win_DATA10.txt"));

            while(file.hasNextLine()) {
                
                ArrayList<String> list = new ArrayList<String>();
                
                for (int l = 0; l < 9; l++) {
                    list.add(file.nextLine());
                }

                // array that represents the scratch board
                String[][] board = new String[3][3];

                // populate the scratch board from these 9 elements in the file
                board[0][0] = list.get(0);
                board[0][1] = list.get(1);
                board[0][2] = list.get(2);
                board[1][0] = list.get(3);
                board[1][1] = list.get(4);
                board[1][2] = list.get(5);
                board[2][0] = list.get(6);
                board[2][1] = list.get(7);
                board[2][2] = list.get(8);

                // counting variables for how many instances of prizes there are on this scratch board
                int blanks = 0, ones = 0, twos = 0, fives = 0, tens = 0, fifties = 0, hundreds = 0, thousands = 0, tenThous = 0, fiveHunThous = 0, millions = 0;

                // represents whether or not at least one prize can be won on the board
                boolean nonePossible = false;

                // loop through each element in the board and count the instances of prizes
                for (int r = 0; r < 3; r++) {
                    for (int c = 0; c < 3; c++) {
                        if (board[r][c].equals("$1")) ones++;
                        if (board[r][c].equals("$2")) twos++;
                        if (board[r][c].equals("$5")) fives++;
                        if (board[r][c].equals("$10")) tens++;
                        if (board[r][c].equals("$50")) fifties++;
                        if (board[r][c].equals("$100")) hundreds++;
                        if (board[r][c].equals("$1000")) thousands++;
                        if (board[r][c].equals("$10000")) tenThous++;
                        if (board[r][c].equals("$500000")) fiveHunThous++;
                        if (board[r][c].equals("$1000000")) millions++;
                        if (board[r][c].equals("?")) blanks++;
                    }
                }

                // if any prize appears 3+ times (a winning prize)
                if (ones > 2 || twos > 2 || fives > 2 || tens > 2 || fifties > 2 || hundreds > 2 || thousands > 2 || tenThous > 2 || fiveHunThous > 2 || millions > 2) {
                    // print the prizes that are won (there should only be 1 winning prize because only one prize can be won per board)
                    if (ones > 2) System.out.println("$1");
                    if (twos > 2) System.out.println("$2");
                    if (fives > 2) System.out.println("$5");
                    if (tens > 2) System.out.println("$10");
                    if (fifties > 2) System.out.println("$50");
                    if (hundreds > 2) System.out.println("$100");
                    if (thousands > 2) System.out.println("$1000");
                    if (tenThous > 2) System.out.println("$10000");
                    if (fiveHunThous > 2) System.out.println("$500000");
                    if (millions > 2) System.out.println("$1000000");
                }
                else { // no prize appears 3 or more times (no definite winner) so check other possibilities (could be more than one possible winner, unlike the clause above)
                    
                    // no prizes are already won and there are 3+ blanks, so any prize could fill in 3 blanks (all prizes are possibilities)
                    if (blanks > 2) System.out.print("$1 $2 $5 $10 $50 $100 $1000 $10000 $500000 $1000000");
                    
                    else if (blanks == 2) { // two spaces are blank
                        // as long as any prize appears more once or more, it could be a winner (could fill in other two blanks)
                        if (ones > 0) System.out.print("$1 ");
                        if (twos > 0) System.out.print("$2 ");
                        if (fives > 0) System.out.print("$5 ");
                        if (tens > 0) System.out.print("$10 ");
                        if (fifties > 0) System.out.print("$50 ");
                        if (hundreds > 0) System.out.print("$100 ");
                        if (thousands > 0) System.out.print("$1000 ");
                        if (tenThous > 0) System.out.print("$10000 ");
                        if (fiveHunThous > 0) System.out.print("$500000 ");
                        if (millions > 0) System.out.print("$1000000 ");

                        // if no instances of dollar prizes
                        if ((ones + twos + fives + tens + fifties + hundreds + thousands + tenThous + fiveHunThous + millions) == 0) {
                            nonePossible = true;
                        }
                    }
                    else if (blanks == 1) { // only one space is blank

                        // the only possible winning prizes must appear more than once already so that it may fill in the last blank and be a winner
                        if (ones > 1) System.out.print("$1 ");
                        if (twos > 1) System.out.print("$2 ");
                        if (fives > 1) System.out.print("$5 ");
                        if (tens > 1) System.out.print("$10 ");
                        if (fifties > 1) System.out.print("$50 ");
                        if (hundreds > 1) System.out.print("$100 ");
                        if (thousands > 1) System.out.print("$1000 ");
                        if (tenThous > 1) System.out.print("$10000 ");
                        if (fiveHunThous > 1) System.out.print("$500000 ");
                        if (millions > 1) System.out.print("$1000000 ");

                        // if all of the prizes appear less than twice, it's impossible to win a prize (one blank and less than two appearances means it cannot appear three times)
                        if (ones < 2 && twos < 2 && fives < 2 && tens < 2 && fifties < 2 && hundreds < 2 && thousands < 2 && tenThous < 2 && fiveHunThous < 2 && millions < 2) {
                            nonePossible = true;
                        }
                    }
                    else if (blanks == 0) { // the board has no blanks (is already full)

                        // prizes can only be won if it appears more than twice (there should be a maximum of one prize won here)
                        if (ones > 2) System.out.print("$1 ");
                        if (twos > 2) System.out.print("$2 ");
                        if (fives > 2) System.out.print("$5 ");
                        if (tens > 2) System.out.print("$10 ");
                        if (fifties > 2) System.out.print("$50 ");
                        if (hundreds > 2) System.out.print("$100 ");
                        if (thousands > 2) System.out.print("$1000 ");
                        if (tenThous > 2) System.out.print("$10000 ");
                        if (fiveHunThous > 2) System.out.print("$500000 ");
                        if (millions > 2) System.out.print("$1000000 ");

                        // all prizes appear less than three times so no prize can be won
                        if (ones < 3 && twos < 3 && fives < 3 && tens < 3 && fifties < 3 && hundreds < 3 && thousands < 3 && tenThous < 3 && fiveHunThous < 3 && millions < 3) {
                            nonePossible = true;
                        }
                    }

                    if (!nonePossible) System.out.println(); // move to next line for next scratch board (there was something to be won on this board)
                    else System.out.println("No Prizes Possible"); // nothing could have been won, so print that there are no prizes possible and move onto next line
                }
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}