The Party, Part II

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:

1. Same colour of item X = < list of people > 2. ColourY for itemX =
2. Not colourY for itemX = The first clue means that the listed people have the same colour for item X; the second clue means that colour of item X for the listed people is Y ; the last clue means that the colour of item X for the listed people is not Y . X is a number from 0 to i − 1 inclusive, indicating the item number. Y is a number from 0 to c − 1 inclusive, indicating the colour number. < list of people > is a list of capital letters in alphabetical order, indicating the list of people that belongs to that clue. All words/letters in a line are separated by a space. There are at most 26 people (from A to Z), 10 items and 10 colours (from 0 to 9). Output For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line. If the clues are inconsistent, or there is a contradiction, then output the line “Contradiction”, otherwise output n lines, indicating the n people, in alphabetical order, the colour of their items in increasing order: P C0 C1 ... Ci−1 for the person represented by letter P, where the colour number of item 0 is C0, the colour number of item 1 is C1 , etc., all separated by a space. If the colour of an item cannot be determined, output “?” for the colour number.

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