#include <bits/stdc++.h> #ifdef ULVI #define db(x) cerr<<"[ "<<#x<<" = "<<(x)<<" ]\n" #define dbv(v) cerr<<#v<<" = [ ";for(auto &__x : v)cerr<<__x<<' ';cerr<<"]\n" #define line() cerr<<string(80, '-')<<'\n' #else #define db(x) #define dbv(v) #define line() #endif #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() #define ff first #define ss second #define enld endl using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef pair<ll,ll> pll; const ll sz=3e5+100; const ll mod=1e9+7; const ll inf=1e18; template<class T> using indexed_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); vector<ll> par(sz),g[sz]; ll findp(ll x){ if(par[x]==x) return x; return par[x]=findp(par[x]); } bool unite(ll a,ll b){ a=findp(a); b=findp(b); if(a==b) return 0; par[b]=a; return 1; } void solve(){ ll n,m,q; cin>>n>>m>>q; vector<pll> less; for(ll i=1;i<=m;i++) par[i]=i; for(ll i=0;i<q;i++){ string s; cin>>s; ll pos=-1; for(ll i=0;i<s.size();i++){ if(s[i]=='<' || s[i]=='='){ pos=i; break; } } ll a=stoll(s.substr(0,pos)),b=stoll(s.substr(pos+1)); if(s[pos]=='<') less.push_back({a,b}); else unite(a,b); } ll comp=1; vector<ll> root(m+5); vector<ll> compid(m+5); map<ll,ll> mp; for(ll i=1;i<=m;i++) root[i]=findp(i); for(ll i=1;i<=m;i++){ ll r=root[i]; if(!mp.count(r)){ mp[r]=comp; compid[i]=comp; comp++; } else compid[i]=mp[r]; } for(auto [a,b]:less) g[compid[a]].push_back(compid[b]); for(ll i=1;i<comp;i++){ if(g[i].empty()) continue; sort(all(g[i])); g[i].erase(unique(all(g[i])),g[i].end()); } vector<ll> indeg(comp+5); for(ll i=1;i<comp;i++) for(ll j:g[i]) indeg[j]++; queue<ll> qq; vector<ll> topo; for(ll i=1;i<comp;i++) if(!indeg[i]) qq.push(i); while(!qq.empty()){ ll node=qq.front(); qq.pop(); topo.push_back(node); for(ll i:g[node]){ indeg[i]--; if(!indeg[i]) qq.push(i); } } vector<ll> mn(comp+5,1),mx(comp+5,n); for(ll i:topo) for(ll j:g[i]) mn[j]=max(mn[j],mn[i]+1); reverse(all(topo)); for(ll i:topo) for(ll j:g[i]) mx[i]=min(mx[i],mx[j]-1); for(ll i=1;i<=m;i++){ ll c=compid[i]; if(mn[c]==mx[c]) cout<<'K'<<mn[c]<<'\n'; else cout<<"?\n"; } } int main(){ //freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout); ios_base::sync_with_stdio(0); cin.tie(0); ll t=1; //cin>>t; for(ll _=1;_<=t;_++){ //cout<<"Scenario #"<<_<<":\n"; solve(); } }