// Problem idea by Thomas Tang  <ttang@cs.queensu.ca>
// Problem written by Thomas Tang
// This ugly solution written by Thomas Tang

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <list>
#include <algorithm>

using namespace std;

int numColour, numItem, numPeople, numClue;

typedef struct {
    int item;
    list<int> people;
} ItemList;

typedef struct {
    int item;
    int colour;
    list<int> people;
} NotList;


void parseRight(char *line, list<int>& people) {
    people.clear();
    char *u;
    u = strtok(line, " ");
    while (u != NULL) {
	people.push_back(u[0] - 'A');
	u = strtok(NULL, " ");
    }
}


// return true if merge is done
bool mergeIfIntersect(list<int>& result, const list<int>& toAdd) {
    list<int>::const_iterator lint, lint2;
    for (lint = toAdd.begin(); lint != toAdd.end(); lint++) {
	lint2 = find(result.begin(), result.end(), *lint);
	if (lint2 != result.end()) {
	    // merge here
	    list<int> temp = toAdd;
	    result.merge(temp);
	    result.unique();
	    return true;
	}
    }
    return false;
}


int main() {
    char line[80], line2[80], *rhs;
    gets(line);
    sscanf(line, "%d%d%d%d", &numPeople, &numItem, &numColour, &numClue);
    // get the clues

    bool people[numPeople][numItem][numColour];
    bool peopleDone[numPeople][numItem];
    int peopleColour[numPeople][numItem];
    list<ItemList> same;
    list<NotList> nots;

    int i, j, k;
    for (i = 0; i < numPeople; i++) {
	for (j = 0; j < numItem; j++) {
	    peopleDone[i][j] = false;
	    for (k = 0; k < numColour; k++) {
		people[i][j][k] = true; // all for now
	    }
	}
    }
    while (numClue--) {
	gets(line);
	int leftItem;
	int leftColour;
	rhs = strstr(line, " = ") + 3;

	if (sscanf(line, "Same colour of item %d", &leftItem) == 1) {
	    ItemList cl;
	    parseRight(rhs, cl.people);
	    // merge if possible
	    list<ItemList>::iterator li;
	    bool found = false;
	    for (li = same.begin(); li != same.end(); li++) {
		if (li->item == leftItem) {
		    found = mergeIfIntersect(li->people, cl.people);
		    if (found) break;
		}
	    }
	    if (!found) {
		cl.item = leftItem;
		same.push_back(cl);
	    }
	} else if (sscanf(line, "Colour %d for item %d",
			  &leftColour, &leftItem) == 2) {
	    ItemList cl;
	    parseRight(rhs, cl.people);
	    list<int>::iterator li;
	    for (li = cl.people.begin(); li != cl.people.end(); li++) {
		const int thisPerson = *li;
		if (peopleDone[thisPerson][leftItem] &&
		    peopleColour[thisPerson][leftItem] != leftColour) {
		    // contradiction
		    printf("Contradiction\n");
		    return 0;
		}
		for (j = 0; j < numColour; j++) {
		    people[thisPerson][leftItem][j] = false;
		}
		people[thisPerson][leftItem][leftColour] = true;
		peopleColour[thisPerson][leftItem] = leftColour;
		peopleDone[thisPerson][leftItem] = true;
	    }
	} else if (sscanf(line, "Not colour %d for item %d",
			  &leftColour, &leftItem) == 2) {
	    NotList nl;
	    parseRight(rhs, nl.people);
	    nl.item = leftItem;
	    nl.colour= leftColour;
	    nots.push_back(nl);
	}
    }
    
    // merge the not-in list with the same list
    // i.e. if A B is the same colour, and B is not 0, then A is also not 0
    list<NotList>::iterator ni;
    for (ni = nots.begin(); ni != nots.end(); ni++) {
	list<ItemList>::iterator li;
	for (li = same.begin(); li != same.end(); li++) {
	    if (ni->item == li->item) {
		mergeIfIntersect(ni->people, li->people);
	    }
	}
	// eliminate now
	list<int>::iterator lint;
	for (lint = ni->people.begin(); lint != ni->people.end(); lint++) {
	    people[*lint][ni->item][ni->colour] = false;
	}
    }

    // refine from "not in" to see if more things can be immediately determined
    for (i = 0; i < numPeople; i++) {
	for (j = 0; j < numItem; j++) {
	    if (peopleDone[i][j]) continue;
	    // -2 == none true (contradiction)
	    // -1 == more than 1 true
	    // 0 or above == exactly one true
	    int lastPossibleColour = -2;
	    for (k = 0; k < numColour; k++) {
		if (people[i][j][k] == true) {
		    if (lastPossibleColour >= 0) {
			lastPossibleColour = -1;
			break;
		    }
		    lastPossibleColour = k;
		}
	    }
	    if (lastPossibleColour >= 0) {
		peopleDone[i][j] = true;
		peopleColour[i][j] = lastPossibleColour;
	    } else if (lastPossibleColour == -2) {
		// none true
		printf("Contradiction\n");
		return 0;
	    }
	}
    }
    
    list<ItemList>::iterator li;
    
    // refine same with known colours
    bool refined = false;
    do {
	refined = false;
	for (li = same.begin(); li != same.end(); li++) {
	    const ItemList& thisSame = *li;
	    int thisItem = thisSame.item;
	    list<int>::const_iterator lint;
	    for (lint = thisSame.people.begin();
		 lint != thisSame.people.end(); lint++) {
		if (peopleDone[*lint][thisItem]) {
		    const int colour = peopleColour[*lint][thisItem];
		    list<int>::const_iterator lint2;
		    for (lint2 = thisSame.people.begin();
			 lint2 != thisSame.people.end(); lint2++) {
			const int thisPerson = *lint2;

			// catch inconsistency
			if (peopleDone[thisPerson][thisItem] &&
			       (peopleColour[thisPerson][thisItem]
				!= colour)) {
			    printf("Contradiction\n");
			    return 0;
			}

			peopleColour[thisPerson][thisItem] = colour;
			peopleDone[thisPerson][thisItem] = true;
		    }
		    refined = true;
		    break;
		}
	    }
	    if (refined) {
		// remove this and try again
		same.erase(li);
		break;
	    }
	}
    } while (refined);
    for (i = 0; i < numPeople; i++) {
	printf("%c", i+'A');
	for (j = 0; j < numItem; j++) {
	    if (peopleDone[i][j]) {
		printf(" %d", peopleColour[i][j]);
	    } else {
		printf(" ?");
	    }
	}
	printf("\n");
    }
    

}