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.
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:
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. 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).
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:
for the person represented by letter P, where the colour number of
item 0 is 
, the colour number of item 1 is 
, etc., all
separated by a space. If the colour of an item cannot be determined,
output ``?'' for the colour number.
4 2 3 6 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
A 2 0 B 2 ? C ? 0 D 2 0
4 2 3 7 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
Contradiction