#include <bits/stdc++.h> #define GOOD_LUCK ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define int long long #define endl "\n" #define ff first #define ss second #define pb push_back #define all(v) v.begin(), v.end() using namespace std; constexpr int MAX = 3e+5 + 1, INF = 2e+16, MOD = 1e+9 + 7, K = 31; int k; deque <pair<int, int>> g[MAX+2]; vector <char> col(MAX+2, 0); vector <int> is(MAX+2, 0), g1[MAX+2]; bool dfs(int u, int d=1) { // cerr << "in " << u << endl; col[u]++; bool ok = 0; if (d == k) is[u] = k; for (auto &i : g[u]) { if (col[i.ff] > 20) continue; if (dfs(i.ff, d+i.ss)) { is[u] = d; } } for (auto &i : g[u]) { if (is[i.ff]) is[u] = is[i.ff] - i.ss; } // cerr << "out " << u << ": " << is[u] << endl; return (is[u]); } struct DSU{ int n; vector <int> par; void init(int n1) { n = n1; par.assign(n+1, -1); } int get(int u) { if (par[u] < 0) return u; return par[u] = get(par[u]); } bool un(int a, int b) { a = get(a); b = get(b); if(a == b) return 0; if (par[a] < par[b]) swap(a, b); par[b] += par[a]; par[a] = b; return 1; } }; vector <int> tp; void srt(int u) { col[u] = 1; for (int &i : g1[u]) { if (col[i]) continue; srt(i); } tp.pb(u); } void _() { int n, m; cin >> k >> n >> m; vector <pair<int, int>> v(n+1, {0, 0}); DSU dsu; dsu.init(n); vector <pair<int, int>> e; while (m--) { int a, b; char c; cin >> a >> c >> b; if (c == '<') { e.pb({a, b}); } else { dsu.un(a, b); } } DSU no; no.init(n); for (auto &i : e) { int a = i.ff, b = i.ss; a = dsu.get(a); b = dsu.get(b); g[a].push_front({b, 1}); // g[b].pb({a, -1}); if (!no.un(a, b)) continue; g1[a].pb(b); } for (int i = 1; i <= n; i++) { if (!col[dsu.get(i)]) srt(dsu.get(i)); } reverse(all(tp)); for (int i = 1; i <= n; i++) col[i] =0; // for (int &i : tp) cerr << i << ' '; for (auto &i : tp) { if (!col[dsu.get(i)]) dfs(dsu.get(i)); } for (int i = 1; i <= n; i++) is[i] = is[dsu.get(i)]; for (int i = 1; i <= n; i++) { if (is[i]) cout << "K" << is[i]; else cout << "?"; cout << endl; } } signed main() { GOOD_LUCK int tests=1; // cin >> tests; for (int i=1; i <= tests; i++) { _(); cout << endl; } return 0; }