Bokrecesioner

문제

En bokrecensent har läst $NN$ böcker som ska recenseras. Varje recension ska avslutas med att boken tilldelas ett betyg på en skala från $11$ till $MM$. Det kan vara svårt att direkt välja ett absolut betyg för varje bok, så bokrecensenten tycker att det är mycket enklare att jämföra två böcker i taget med varandra och beskriva vilken av dem som är bäst.

Bokrecensenten har numrerat böcker med heltal från $11$ till $NN$ och vill nu bestämma deras betyg $a_1,a_2,\dots ,a_{N}a\_1,\; a\_2,\; \backslash dots\; ,\; a\_N$. För att göra det har bokrecensenten gjort $RR$ jämförelser som beskriver relationen mellan $a_{i}a\_i$ och $a_{j}a\_j$, för några böcker $i,ji,\; j$.

Bokrecensenten är nöjd med vilken betygsättning som helst, så länge alla krav från jämförelserna är uppfyllda. Hjälp bokrecensenten att hitta en sådan betygsättning.

입력

Första raden består av tre heltal, $NN$ ($1\le N\le 1000001\; \backslash leq\; N\; \backslash leq\; 100\backslash ,000$), $MM$ ($1\le M\le 1000001\; \backslash leq\; M\; \backslash leq\; 100\backslash ,000$), $RR$ ($1\le R\le 5000001\; \backslash leq\; R\; \backslash leq\; 500\backslash ,000$) -- antalet böcker, högsta möjliga betyget och antalet jämförelser.

Sedan följer $RR$ rader med relationer som ska vara uppfyllda. Varje sådan rad har formatet "<i> <relation> <j>", som beskriver relationen mellan $a_{i}a\_i$ och $a_{j}a\_j$. $ii$ och $jj$ är heltal mellan $11$ och $NN$, $i\mathrm{\ne }ji\; \backslash neq\; j$. Relationen $rr$ är någon av strängarna '<', '=', '≤', och detta beskriver just att $a_{i}a\_i$ <relation> $a_{j}a\_j$ måste gälla. Inget par av böcker kommer att jämföras mer än en gång.

출력

Skriv ut en lista med heltal $a_1,a_2,\dots ,a_{N}a\_1,\; a\_2,\; \backslash ldots\; ,\; a\_N$ sådan att alla relationer håller, och alla tal är på intervallet $[1,M][1,\; M]$. Om det finns flera lösningar, skriv ut vilken som helst. Om det är omöjligt, skriv ut $-1-1$.

힌트

I det första indataexemplet så är 1 2 1 3 3 en giltig lösning. Detta kan verifieras genom att se att alla tal ligger på intervallet $[1,3][1,\; 3]$, och att talen uppfyller de fyra relationerna , , och .