/* _ __ __ __ ____ ___ _ __ | | /| / / ___ _ / /_ ____ / / / __ \ ___ ___ / _ \ (_) ___ ____ ___ / / | |/ |/ / / _ `// __// __/ / _ \ / /_/ / / _ \/ -_) / ___/ / / / -_)/ __// -_) /_/ |__/|__/ \_,_/ \__/ \__/ /_//_/ \____/ /_//_/\__/ /_/ /_/ \__/ \__/ \__/ (_) */ #pragma GCC optimize("O3") #pragma GCC optimize ("unroll-loops") // #pragma GCC target("avx2") #include <bits/stdc++.h> #define ll long long #define ull unsigned ll #define ld long double #define all(v, l) v.begin() + l, v.end() #define rall(v, l) v.rbegin(), v.rend() - l #define pb push_back #define rsz resize #define fi first #define se second #define LMAX LLONG_MAX #define LMIN LLONG_MIN #define IMAX INT_MAX #define IMIN INT_MIN #define endl "\n" #define newline cout << endl; using namespace std; // constants // functions int GCD(int A, int B); int LCM(int A, int B); int power(int base, int exponent); // structs struct dsu { vector <int> par; void cleanse() { iota(all(par, 0), 0); } void prep(int n) { par.rsz(n); cleanse(); } int get(int v) { if (v == par[v]) { return v; } return par[v] = get(par[v]); } void unite(int u, int v) { u = get(u), v = get(v); if (u == v) { return; } par[u] = v; } }; struct graph { vector <vector <int> > g; vector <int> dist, in; void prep(int n) { g.rsz(n); dist.rsz(n); in.rsz(n); fill(all(in, 0), 0); } void add(int u, int v) { g[u].pb(v); in[v]++; } void build() { queue <int> q; for (int v = 1; v < (int)in.size(); v++) { if (!in[v]) { q.push(v); dist[v] = 1; } } while (!q.empty()) { auto v = q.front(); q.pop(); for (auto u : g[v]) { dist[u] = max(dist[u], dist[v] + 1); in[u]--; if (!in[u]) { q.push(u); } } } } }; // globals // variables int K, n, m; // iterators int i; // notes /* My favorite anime is One Piece(obviously) My oshi(Yes, I have an oshi, deal with it) is Kamil_Tsubaki -stuff you should look for- * int overflow, array bounds * special cases (n=1?) * do something instead of nothing and stay organized * WRITE STUFF DOWN * DON'T GET STUCK ON ONE APPROACH continue - skip the rest in the loop */ void solve() { cin >> K >> n >> m; vector <pair <char, pair <int, int> > > edges(m + 1); for (i = 1; i <= m; i++) { cin >> edges[i].se.fi >> edges[i].fi >> edges[i].se.se; } dsu D; D.prep(n + 1); for (i = 1; i <= m; i++) { if (edges[i].fi == '=') { D.unite(edges[i].se.fi, edges[i].se.se); } } graph G, RG; G.prep(n + 1), RG.prep(n + 1); for (i = 1; i <= m; i++) { if (edges[i].fi == '=') { continue; } auto &[u, v] = edges[i].se; if (edges[i].fi == '>') { swap(u, v); } u = D.get(u), v = D.get(v); G.add(u, v); RG.add(v, u); } G.build(); RG.build(); for (i = 1; i <= n; i++) { auto v = D.get(i); if (G.dist[v] + RG.dist[v] - 1 == K) { cout << 'K' << G.dist[v]; } else { cout << '?'; } newline } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int t = 1; // cin >> t; while (t--) { solve(); } } int GCD(int A, int B) { if (!A) { return B; } return GCD(B % A, A); } int LCM(int A, int B) { return A * B / GCD(A, B); } int power(int base, int exponent) { int res = 1; while (exponent) { if (exponent & 1) { res *= base; } base *= base; exponent >>= 1; } return res; } /* $$$$$$$$\ $$$$$$$$\ $$ _____|\____$$ | $$ | $$ / $$$$$\ $$ / $$ __| $$ / $$ | $$ / $$$$$$$$\ $$$$$$$$\ \________|\________| */