#include <bits/stdc++.h> using namespace std; #define int long long #define all(v) v.begin(), v.end() #define rall(v) v.rbegin(), v.rend() const int sz = 3e5 + 5, inf = 1e18, mod = 1e9 + 7, lg = 23; int dis[sz], disr[sz]; bool vis1[sz], vis2[sz]; vector<int> g[sz], gr[sz], tp, tpr; struct DSU { int n; vector<int> par; void init(int _n) { n = _n; par.assign(n + 1, -1); } int find(int a){ if (par[a] < 0) return a; return par[a] = find(par[a]); } bool unite(int a, int b) { a = find(a); b = find(b); if (a == b) return 0; if (par[a] < par[b]) swap(a, b); par[b] += par[a]; par[a] = b; return 1; } }; void dfs1(int node){ vis1[node] = 1; for (int to : g[node]) { if (!vis1[to]) { dfs1(to); } } tp.push_back(node); } void dfs2(int node){ vis2[node] = 1; for (int to : gr[node]) { if (!vis2[to]) { dfs2(to); } } tpr.push_back(node); } void _(){ int n, m, v; cin >> n >> m >> v; DSU dsu; dsu.init(m); vector<pair<int, int>> ed; for (int i = 1; i <= v; i++) { int a, b; char op; cin >> a >> op >> b; if (op == '=') { dsu.unite(a, b); } else { ed.push_back({a, b}); } } for (auto [x, y] : ed) { x = dsu.find(x); y = dsu.find(y); g[x].push_back(y); gr[y].push_back(x); } for (int i = 1; i <= m; i++) { int r = dsu.find(i); if (!vis1[r]) { dfs1(r); } } for (int i = 1; i <= m; i++) { int r = dsu.find(i); if (!vis2[r]) { dfs2(r); } } reverse(all(tp)); reverse(all(tpr)); for (auto x : tp) { for (auto to : g[x]) { dis[to] = max(dis[to], dis[x] + 1); } } for (auto x : tpr) { for (auto to : gr[x]) { disr[to] = max(disr[to], disr[x] + 1); } } for (int i = 1; i <= m; i++) { int r = dsu.find(i); if (dis[r] + disr[r] + 1 < n) { cout << "?" << endl; } else cout << "K" << dis[r] + 1 << endl; } } signed main(){ cin.tie(nullptr)->sync_with_stdio(0); int T = 1; // cin >> T; while (T--) _(); }