Coin type identification

Mirko visited a distant country where nobody uses banknotes, only coins. The country has $N$ types of coins in circulation, named K1, K2, K3, ..., KN. All coins have the same size and shape, but their weights differ. K1 is the lightest type, K2 is the second lightest, and so on up to KN, the heaviest type.

Mirko has $M$ coins in his pocket and does not know which type each one is. The only tool he has for finding out is a simple balance scale.

Mirko first labelled his unknown coins with the numbers $1$ through $M$, and then performed $V$ weighings. In one weighing he puts one coin on one side of the scale and another coin on the other side. He then sees whether the two coins weigh the same, and if they do not, which one is heavier.

Write a program that uses the weighing results to determine the type of every coin whose type is fixed by those results.

The first line contains the integers $N$, $M$ and $V$: the number of coin types in the country, the number of coins in Mirko's pocket, and the number of weighings.

Each of the next $V$ lines holds the result of one weighing in the form ACB, where $A$ and $B$ are different positive integers not greater than $M$, and $C$ is the character = (equal) or < (lighter).

There is no space between the numbers and the character $C$. One weighing result says that Mirko's coin numbered $A$ weighs the same as the coin numbered $B$, or is lighter than it.

The weighing results are never contradictory.

Print $M$ lines. Line $i$ must contain the type of the coin numbered $i$, written as KX, where $X$ is an integer between $1$ and $N$.

If the type of the coin numbered $i$ cannot be determined uniquely, print the character ? on line $i$.

In all subtasks, $2 \le N \le 300\,000$, $2 \le M \le 300\,000$ and $1 \le V \le 300\,000$.