#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct Node {
vector<int> parents; // Item pos
vector<int> children;
Node* root = nullptr;
int depth = -1;
};
struct Item {
Node* node = nullptr;
int coinNum = -1;
};
int N,M,V;
vector<Item> items;
vector<int> dsu;
int dfs(bool goUp, bool setDepth, Node* node, int depth, Node* root) {
if (goUp && !node->parents.empty()) { // go up to parent
for (const auto& parent : node->parents) {
dfs(true, false, items[parent].node, 1, nullptr);
}
} else if (!setDepth) { // find N long path (if you find val with depth set go up and set?)
if (depth == N) return N;
int maxD = 0;
for (const auto& child : node->children) {
maxD = max(maxD, dfs(false, false, items[child].node, depth+1, nullptr));
}
if (node->parents.empty() && maxD == N) {
node->depth = 1;
for (const auto& child : node->children) {
dfs(false, true, items[child].node, node->depth + 1, node);
}
}
if (maxD == N) return N;
} else { // set depth
node->depth = depth;
for (const auto& child : node->children) {
dfs(false, true, items[child].node, node->depth + 1, root);
}
}
return 0;
}
int findR(int a) {
int p = dsu[a];
if (p != -1) return dsu[a] = findR(p);
return a;
}
void unionR(int a, int b) {
if (findR(a) == findR(b)) return;
else dsu[findR(a)] = findR(b);
}
int main() {
scanf("%d %d %d",&N,&M,&V);
items.resize(M, Item{nullptr, -1});
vector<pair<int, int>> equal;
vector<pair<int, int>> less;
for (int i = 0; i < V; i++) {
int A,B; char C; scanf("%d %c %d", &A, &C,&B);
A--;
B--;
if (C == '=') {
equal.push_back({A,B});
} else { // A < B
less.push_back({A,B});
}
}
// DSU for equality than less
dsu.resize(M, -1);
for (int i = 0; i < equal.size(); i++) {
auto e = equal[i];
unionR(e.first, e.second);
}
for (int i = 0; i < less.size(); i++) {
auto l = less[i];
int p = findR(l.first);
int c = findR(l.second);
if (!items[c].node) items[c].node = new Node{{}, {}, nullptr, -1};
if (!items[p].node) items[p].node = new Node{{}, {}, nullptr, -1};
items[c].node->parents.push_back(p);
items[p].node->children.push_back(c);
}
for (int i = 0; i < items.size(); i++) {
if (items[i].node && items[i].node->depth == -1) {
dfs(true, false, items[i].node, 1, nullptr);
}
}
for (int i = 0; i < items.size(); i++) {
int coinNum = -1;
int r = findR(i);
if (items[r].node) coinNum = items[r].node->depth;
if (coinNum == -1) printf("?\n");
else printf("K%d\n", coinNum);
}
// dfs -> go to all parents until empty -> then start dfs and get max of all children and see if == N -> if yes then go to all children and set depth
// if during dfs -> depth of a child is set -> then set all other depths based on it
// iterate over items and start dfs (if somewhere depth != -1 -> go up and set everything accordingly)
// at end if depth == -1 -> ? otherwise depth = Coin num
return 0;
}
