/*
Telebe of Adicto && Mamedov yani AzeTurk810
I see humans but no humanity
*/
#include <algorithm>
#include <cassert>
#include <functional>
#include <iostream>
#include <utility>
#include <vector>
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll = long long;
using namespace std;
#define ln '\n'
#define INFi 1e9
#define INFll 1e18
#ifdef ONPC
#include <algo.hpp>
#else
#define dbg(...)
#define dbg_out(...)
#endif
struct DSU {
vector<int> par;
int n, components;
DSU(int _n) {
n = _n;
components = n;
par.assign(n, -1);
}
int Find(int u) {
if (par[u] < 0)
return u;
return par[u] = Find(par[u]);
}
bool Union(int u, int v) {
u = Find(u);
v = Find(v);
if (u != v) {
components--;
if (par[u] > par[v]) {
swap(u, v);
}
par[u] += par[v];
par[v] = u;
return true;
} else {
return false;
}
}
};
char solve() {
int N, M, V;
if (!(cin >> N >> M >> V))
return 1;
DSU t(M);
vector<vector<int>> g(M), gr(M);
for (int _ = 0; _ < V; _++) {
int u;
cin >> u;
char c;
cin >> c;
int v;
cin >> v;
u--, v--;
if (c == '=') {
t.Union(u, v);
} else {
g[v].push_back(u);
gr[u].push_back(v);
}
}
vector<int> lvl(M, -1), ans(M, -1);
function<void(int)> dfs = [&](int v) {
if (g[v].size() == 0)
lvl[v] = 1;
if (lvl[v] != -1)
return;
for (auto u : g[v]) {
dfs(u);
lvl[v] = max(lvl[v], lvl[u] + 1);
}
// return 1;
};
vector<char> used(M, false);
function<void(int)> dfs2 = [&](int v) {
used[v] = true;
ans[v] = lvl[v];
dbg(v);
for (auto u : g[v]) {
if (used[u] || (lvl[u] != lvl[v] - 1))
continue;
dfs2(u);
}
};
dbg(gr);
dbg(g);
for (int i = 0; i < M; i++) {
if (t.Find(i) == i)
continue;
for (auto u : g[i]) {
gr[t.Find(i)].push_back(u);
}
for (auto u : gr[i]) {
g[u].push_back(t.Find(i));
}
}
for (int i = 0; i < M; i++) {
if (lvl[t.Find(i)] == -1 && gr[t.Find(i)].empty()) {
dfs(t.Find(i));
// lvl[i] = lvl[t.Find(i)];
}
}
dbg(lvl);
for (int i = 0; i < M; i++) {
if (lvl[t.Find(i)] == N) {
dfs2(t.Find(i));
}
}
for (int i = 0; i < M; i++) {
dbg(i);
dbg(t.Find(i));
ans[i] = ans[t.Find(i)];
}
for (int i = 0; i < M; i++) {
assert(ans[i] <= N);
if (ans[i] == -1) {
cout << "?\n";
} else {
cout << "K" << ans[i] << "\n";
}
}
dbg(gr);
dbg(g);
// dbg(used);
return 0;
}
// Attack on titan<3
signed main() {
ios::sync_with_stdio(0);
cin.tie(nullptr);
int t = 1e9;
// cin >> t;
for (int cases = 0; cases < t; cases++) {
if (solve())
break;
#ifdef ONPC
cerr << "__________\n";
#endif
}
}
// Just Imaginary
/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣀⠀⠀⠀⢀⣴⣾⠀⠀⠀⡀⢀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⣦⣾⣿⣿⣿⣿⣿⡆⠁⠀⢀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⣿⣿⣿⣿⣿⣿⣿⣿⡿⠁⠀⡠⠂⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠠⠔⠚⣿⣿⣿⣿⣿⣦⡄⠀⠁⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢀⠠⠐⢂⠉⡀⣀⣤⣄⢻⣿⣿⡟⢈⡹⣿⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⡀⠄⠂⠈⠀⣶⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠘⣷⡀⠀⡀⠐⠂⠐⢄
⠀⠀⠀⠀⠀⠀⠀⣿⣿⠟⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⣀⣾⣷⠯⠀⠤⠤⠄⠈
⠀⠀⠀⠀⠀⠀⣼⣿⡟⠀⠀⣹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⣰⣿⠋⠀⠀⢠⣾⣿⣿⣿⣿⣿⣭⠟⢻⣿⣿⣿⣿⡿⠁⠀⠀⠀⠀
⠀⠀⠀⣀⣶⡟⠁⠀⢾⣶⣿⠟⠉⠈⢻⣿⣿⣿⣦⣜⠀⠛⠛⠿⠁⠀⠀⠀⠀⠀
⠚⠻⠿⠿⡿⠁⠀⢠⣿⣿⠁⠀⣠⠖⠋⠉⠻⣿⣿⣿⣶⡀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⣰⣿⡿⠃⠠⠊⠁⠀⠀⠀⠀⠈⢿⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⢀⣴⡿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⣠⣾⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⢀⣴⠾⠟⠛⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
*/
