import java.util.Scanner;

import java.util.*;

public class Solver {

    static ArrayList <Integer> minterms = new ArrayList <Integer>();
    static ArrayList <Integer> dontcares = new ArrayList <Integer>();
    static ArrayList <ArrayList <ArrayList<String>>> comparisons = new ArrayList <ArrayList <ArrayList <String>>>();
    static ArrayList <String> primeImplicants = new ArrayList <String>();
    static String [] combination = new String[26];

    static int MaxnumberOf_Vars;
    static boolean foundCombination = false;

    static Scanner in = new Scanner(System.in);

    private static void fillArrayList() {
        for(int i=0; i<26; i++)  {
            comparisons.add(new ArrayList()); //comparisons
            for(int j=0; j<MaxnumberOf_Vars; j++)
                comparisons.get(i).add(new ArrayList()); // groups
        }
    }

    private static int find_numOfvars()
    {
        int  maxMinterm = 0,maxDontCare=0;
        if (minterms.isEmpty()==false)
             maxMinterm = Collections.max(minterms);
        if (dontcares.isEmpty()==false)
             maxDontCare = Collections.max(dontcares);

        int maxImplicant = Math.max(maxDontCare, maxMinterm);
        float exponent =  (float) (Math.log(maxImplicant) / Math.log(2));
        if ((exponent - (int)exponent)==0)
            return Math.round((float)(Math.log((double)(maxImplicant))/(Math.log(2.0))))+1;
        else
            return Math.round((float)(Math.log((double)(maxImplicant))/(Math.log(2.0))));
    }

    private static String differBinary(String firstMinterm, String secondMinterm) {
        String result = "";
        int ones=0;
        for(int i=0; i<firstMinterm.length(); i++) {
            if(firstMinterm.charAt(i) != secondMinterm.charAt(i))
                result += "-";
            else
                result += firstMinterm.charAt(i);
            if(firstMinterm.charAt(i)=='1')
                ones++;
        }
        return result + " " + String.valueOf(ones);
    }


    private static void decimalToBinary() {

        for(int i=0; i<minterms.size(); i++) {
            int div = minterms.get(i), ones = 0;
            String res= "";
            while(div!=0) {
                if(div%2==1) {
                    ones++;
                    res = "1" + res;
                }
                else
                    res = "0" + res;
                div/=2;
            }
            for(int j=0, len = res.length(); j<MaxnumberOf_Vars-len; j++)
                res = "0" + res;
            comparisons.get(0).get(ones).add(res + " " + Integer.parseInt(res,2));
        }
        for(int i=0; i<dontcares.size();i++) {
            int div = dontcares.get(i), ones = 0;
            String res = "";
            while(div!=0) {
                if(div%2==1) {
                    ones++;
                    res = "1" + res;
                }
                else
                    res = "0" + res;
                div/=2;
            }
            for(int j=0, len = res.length(); j<MaxnumberOf_Vars-len; j++)
                res = "0" + res;
            comparisons.get(0).get(ones).add(res + " " + Integer.parseInt(res,2));
        }
        for(int i=0; i< comparisons.get(0).size(); i++)
            Collections.sort(comparisons.get(0).get(i));
    }

    private static void doComparisons() {
        int k;
        for(k=0; k<comparisons.size()-1; k++) { //comparisons
            boolean[][] takenToNextComparison = new boolean[10][100];
            for(int l=0; l<comparisons.get(k).size(); l++) { //groups
                if(comparisons.get(k).get(l).isEmpty())
                    continue;
                int m = l+1;

                while(m< comparisons.get(k).size() && comparisons.get(k).get(m).isEmpty())
                    m++;
                if(m==comparisons.get(k).size()) {
                    for(int i=0; i< comparisons.get(k).get(l).size(); i++) {
                        if(!takenToNextComparison[l][i]) {
                            ArrayList <String> iData = new ArrayList <String>();
                            for(String retval: comparisons.get(k).get(l).get(i).split(" "))
                                iData.add(retval);
                            String info = iData.get(0);
                            for(int x=1; x<iData.size(); x++)
                                info += " " + iData.get(x);
                            primeImplicants.add(info);
                        }
                    }
                    break;
                }
                for(int i=0; i<comparisons.get(k).get(l).size(); i++) {
                    boolean fPrime = true;
                    ArrayList <String> iData = new ArrayList <String>();
                    for(String retval: comparisons.get(k).get(l).get(i).split(" "))
                        iData.add(retval);
                    for(int j=0; j<comparisons.get(k).get(m).size(); j++) {
                        ArrayList <String> jData = new ArrayList <String>();
                        for(String retval: comparisons.get(k).get(m).get(j).split(" "))
                            jData.add(retval);
                        float exponent = 0;
                        int difference = 0;
                        boolean fAccept = true;
                        for(int x=1; x<iData.size(); x++) {
                            int iDifference = Integer.parseInt(iData.get(x));
                            int jDifference = Integer.parseInt(jData.get(x));
                            int tempDifference = jDifference - iDifference;
                            float tempExponent = (float) (Math.log(tempDifference) / Math.log(2));
                            if(x==1) {
                                difference = tempDifference;
                                exponent =  tempExponent;
                                if(difference<0 || exponent - (int) exponent!=0) {
                                    fAccept = false;
                                    break;
                                }
                            }
                            else {
                                if(tempDifference!=difference || tempExponent!=exponent) {
                                    fAccept = false;
                                    break;
                                }
                            }
                        }
                        if(fAccept) {
                            fPrime = false;
                            String iBinary = iData.get(0);
                            String jBinary = jData.get(0);
                            takenToNextComparison[l][i] = true;
                            takenToNextComparison[m][j] = true;
                            ArrayList <String> dashesAndOnes = new ArrayList <String>();
                            for( String retval: differBinary(iBinary, jBinary).split(" "))
                                dashesAndOnes.add(retval);
                            String differenceBinary = dashesAndOnes.get(0);
                            int ones = Integer.parseInt(dashesAndOnes.get(1));
                            boolean fDuplicate = false;
                            for(int x=0; x<comparisons.get(k+1).size(); x++) {
                                for(int y=0; y<comparisons.get(k+1).get(x).size(); y++) {
                                    String duplicate = comparisons.get(k+1).get(x).get(y).split(" ")[0];
                                    if(duplicate.equals(differenceBinary)) {
                                        fDuplicate = true;
                                        break;
                                    }
                                }
                            }
                            if(!fDuplicate) {
                                String info = differenceBinary;
                                for(int x=1; x< iData.size(); x++) {
                                    info += " " + iData.get(x);
                                }
                                for(int x=1; x< jData.size(); x++) {
                                    info += " " + jData.get(x);
                                }
                                comparisons.get(k+1).get(ones).add(info);
                            }
                            else
                                continue;

                        }
                    }
                if(fPrime && !takenToNextComparison[l][i]) {
                    String info = iData.get(0);
                    for(int x=1; x<iData.size(); x++)
                        info += " " + iData.get(x);
                    primeImplicants.add(info);
                }

            }
        }
    }
    for(int i=0; i<comparisons.get(k).size(); i++) //groups
        for(int j=0; j<comparisons.get(k).get(i).size(); j++) {
            ArrayList <String> data = new ArrayList <String>();
            for(String retval: comparisons.get(k).get(i).get(j).split(" "))
                data.add(retval);
            String info = data.get(0);
            for(int x=1; x<data.size(); x++)
                info += " " + data.get(x);
            primeImplicants.add(info);
        }
    }

    private static String find_Expression(ArrayList a)
    {
        String expression = new String ();
        ;
        StringBuilder Dashes_expression = null;
        StringBuilder expression_Builder = new StringBuilder();
        ///I want to know the maximum estimated number of variables;

        for (int i=0 ; i<a.size() ; i++ )
        {
            for( String retval: ((String) a.get(i)).split(" ")){
                 Dashes_expression = new StringBuilder();
                Dashes_expression.append(retval);
                break;
            }

            for (int j=0 ; j < Dashes_expression.length();j++)
            {
              if (Dashes_expression.charAt(j)=='1')
              {
                  char character = (char) ((int)('A')+j);
                  expression_Builder.append(character);
              }
              else if (Dashes_expression.charAt(j)=='0')
              {
                  char character = (char) ((int)('A')+j);
                  String str = new String();
                  str += character + "'";
                  expression_Builder.append(str);

              }

            }
            if (i!=(a.size()-1))
                 expression_Builder.append(" + ");
        }

        expression = expression_Builder.toString();
        return expression;
    }

    private static boolean checkCombination(int len) {
        ArrayList<Integer> checkedMinterms = new ArrayList<Integer>();

        for(int i=0; i<len; i++) {
            ArrayList <String> data = new ArrayList <String>();
            for(String retval: combination[i].split(" " ))
                data.add(retval);
            for(int j=1; j<data.size(); j++)
                checkedMinterms.add(Integer.parseInt(data.get(j)));
        }
        if(checkedMinterms.containsAll(minterms))
            return true;
        else
            return false;
    }

    private static void generateCombinations(int element, int m, int len) { //(1,0,size)
        if(m == len) {
            if(checkCombination(len)) {
                foundCombination = true;
                return;
            }
            return;
        }
        if(element== primeImplicants.size()+1)
            return;
        combination[m] = primeImplicants.get(element-1);
        if(!foundCombination)
            generateCombinations(element+1, m+1, len);
        if(!foundCombination)
            generateCombinations(element+1, m, len);

    }



    public static void main (String[] args) {
        System.out.println("Enter the minterms in decimal <-1 to finish>:");
        while(true) {
            int input;
            input = in.nextInt();
            if(input==-1)
                break;
            minterms.add(input);
        }
        System.out.println("Enter the dontcares in decimal <-1 to finish>:");
        while(true) {
            int input;
            input = in.nextInt();
            if(input==-1)
                break;
            dontcares.add(input);
        }
        MaxnumberOf_Vars = find_numOfvars();
        fillArrayList();
        decimalToBinary();
        doComparisons();

        for(int k=0; k<comparisons.size(); k++) {
            boolean comparisonHasElements = false;

            for(int i=0; i<comparisons.get(k).size(); i++) {
                if(comparisons.get(k).get(i).isEmpty())
                    continue;
                for(int j=0; j<comparisons.get(k).get(i).size(); j++) {
                    System.out.println(comparisons.get(k).get(i).get(j));
                }
                comparisonHasElements = true;
                System.out.println("-----------------");
            }
            if(comparisonHasElements) {
                System.out.println("______________________________________________________");
                System.out.println();
            }
        }
        System.out.println("Prime Implicants:");
        for(int i=0; i<primeImplicants.size(); i++) {
            System.out.println(primeImplicants.get(i));
        }
        System.out.println();
        System.out.println(find_Expression(primeImplicants));
        System.out.println();
        System.out.println();
        int numberOfEssential = 0;
        for(int i=1; i<=primeImplicants.size(); i++) {
            generateCombinations(1  , 0, i);
            if(foundCombination) {
                numberOfEssential = i;
                break;
            }
        }
        System.out.println("Essential Prime Implicants:");
        ArrayList<String> essential = new ArrayList<String>();
        for(int i=0; i< numberOfEssential; i++ ) {
            System.out.println(combination[i]);
            essential.add(combination[i]);
        }
        System.out.println();
        System.out.println(find_Expression(essential));
    }
}