Every person's blood has 2 markers called ABO alleles. Each of the markers is represented by one of three letters: A, B, or O. This gives six possible combinations of these alleles that a person can have, each of them resulting in a particular ABO blood type for that person.

Likewise, every person has two alleles for the blood Rh factor, represented by the characters + and -. Someone who is ``Rh positive" or ``Rh+" has at least one + allele, but could have two. Someone who is ``Rh negative" always has two - alleles.

The blood type of a person is a combination of ABO blood type and Rh factor. The blood type is written by suffixing the ABO blood type with the + or - representing the Rh factor. Examples include A+, AB-, and O-.

Blood types are inherited: each biological parent donates one ABO allele (randomly chosen from their two) and one Rh factor allele to their child. Therefore 2 ABO alleles and 2 Rh factor alleles of the parents determine the child's blood type. For example, if both parents of a child have blood type A-, then the child could have either type A- or type O- blood. A child of parents with blood types A+ and B+ could have any blood type.

In this problem, you will be given the blood type of either both parents or one parent and a child; you will then determine the (possibly empty) set of blood types that might characterize the child or the other parent.

Note: an uppercase letter ``Oh" is used in this problem to denote blood types, not a digit (zero).

Input 

The input consists of multiple test cases. Each test case is on a single line in the format: the blood type of one parent, the blood type of the other parent, and finally the blood type of the child, except that the blood type of one parent or the child will be replaced by a question mark. To improve readability, whitespace may be included anywhere on the line except inside a single blood type specification.

The last test case is followed by a line containing the letters E, N, and D separated by whitespace.

Output 

For each test case in the input, print the case number (beginning with 1) and the blood type of the parents and the child. If no blood type for a parent is possible, print ``IMPOSSIBLE". If multiple blood types for parents or child are possible, print all possible values in a comma-separated list enclosed in curly braces. The order of the blood types inside the curly braces does not matter.

The sample output illustrates multiple output formats. Your output format should be similar.

Sample Input 

O+  O-  ? 
O+  ?  O-
AB-  AB+  ? 
AB+  ?  O+ 
E N D

Sample Output 

Case 1: O+ O- {O+, O-}
Case 2: O+ {A-, A+, B-, B+, O-, O+} O-
Case 3: AB- AB+ {A+, A-, B+, B-, AB+, AB-}
Case 4: AB+ IMPOSSIBLE O+

先推論一下所有可能來簡化程式，如果是顯性性狀，則考慮其中一個隱性基因即可，發現不影響結果。


#include <stdio.h>
#include <iostream>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
map<string, string> TYPE;
void print(set<string> ret) {
    if(ret.size() == 0) {
        printf("IMPOSSIBLE");
        return;
    }
    if(ret.size() > 1)
        printf("{");
    for(set<string>::iterator it = ret.begin();
        it != ret.end(); it++) {
        if(it != ret.begin())   cout << ", ";
        cout << *it;
    }
    if(ret.size() > 1)
        printf("}");
}
set<string> child(string a, string b) {
    string rha, rhb;
    set<string> ret;
    int i, j, k;
    rha = a.substr(a.size()-1, 1);
    rhb = b.substr(b.size()-1, 1);
    a = a.substr(0, a.size()-1);
    b = b.substr(0, b.size()-1);
    if(a == "A")        a = "AO";
    else if(a == "B")   a = "BO";
    else if(a == "O")   a = "OO";
    if(b == "A")        b = "AO";
    else if(b == "B")   b = "BO";
    else if(b == "O")   b = "OO";
    for(i = 0; i < 2; i++) {
        for(j = 0; j < 2; j++) {
            string comb = "";
            comb += a[i];
            comb += b[j];
            string ss = TYPE[comb];
            if(rha == "-" && rhb == "-") {
                ret.insert(ss+"-");
            } else {
                ret.insert(ss+"+");
                ret.insert(ss+"-");
            }
        }
    }
    return ret;
}
set<string> parent(string a, string c) {
    set<string> ret;
    string tt[] = {"A", "B", "AB", "O"};
    int i;
    for(i = 0; i < 4; i++) {
        set<string> tmp1 = child(a, tt[i]+"+");
        if(tmp1.find(c) != tmp1.end())
            ret.insert(tt[i]+"+");
        set<string> tmp2 = child(a, tt[i]+"-");
        if(tmp2.find(c) != tmp2.end())
            ret.insert(tt[i]+"-");
    }
    return ret;
}
int main() {
    TYPE["AA"] = "A", TYPE["AO"] = "A", TYPE["AB"] = "AB";
    TYPE["BA"] = "AB", TYPE["BO"] = "B", TYPE["BB"] = "B";
    TYPE["OA"] = "A", TYPE["OO"] = "O", TYPE["OB"] = "B";
    string PA, PB, C;
    int cases = 0;
    while(cin >> PA >> PB >> C) {
        if(PA == "E") break;
        printf("Case %d: ", ++cases);
        if(C == "?") {
            cout << PA << " " << PB << " ";
            set<string> ret = child(PA, PB);
            print(ret);
            puts("");
        } else if(PA == "?") {
            set<string> ret = parent(PB, C);
            print(ret);
            cout << " " << PB << " " << C << endl;
        } else {
            set<string> ret = parent(PA, C);
            cout << PA << " ";
            print(ret);
            cout << " " << C << endl;
        }
    }
    return 0;
}
// O- O- ?