In the middle of the party, Donna Anna, Donna Elvira, and Don Ottavio arrive masked, and intent to confront Don Giovanni when they find him. You, as a guest of the party, know what they want to do. You want to stay out of trouble, so you would like to keep away from them. But they mask themselves along with other guests, and you have trouble identifying them. Fortunately, you have collected a set of clues from other guests. You have to analyse them and find out who is who. Input The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs. The input starts with a line with 4 positive numbers, n, i, c, and u, separated by a space. n is the number of people in the set of clues, i is the number of items (such as shoes, masks, clothes, etc.) that can be identified by colours, c is the number of possible colours. The rest of input consists of u lines of clues. There are three types of clues:
2/2 Sample Input 2 4236 Same colour of item 0 = A B D Colour 2 for item 0 = B Not colour 2 for item 1 = C Not colour 1 for item 1 = C Same colour of item 1 = C D Same colour of item 1 = A D 4237 Same colour of item 0 = A B D Colour 2 for item 0 = B Not colour 2 for item 1 = C Not colour 1 for item 1 = C Same colour of item 1 = C D Same colour of item 1 = A D Colour 1 for item 0 = D Sample Output A20 B2? C?0 D20 Contradiction