COI '14 #2 Kovanice

Points: 15 (partial)

Time limit: 2.0s

Memory limit: 512M

Problem type

Mirko paid a touristic visit to a land far away where banknotes aren't used, but only coins. More precisely, the country has $N$ ~N~ types of coins in circulation. Their names are, respectively, K1, K2, …, KN. The coins are of the same size and shape, but different weights. K1 is the lightest type of coin, K2 is the second lightest and so on until the heaviest type KN.

Mirko has $M$ ~M~ coins in his pocket, but he doesn't know which one is of which type. In order to determine that, he only has a simple balance scale at his disposal.

Initially, Mirko marked his unknown coins with numbers from $1$ ~1~ to $M$ ~M~ and after that performed $V$ ~V~ weighings. In each weighing, he put one coin on one side of the scale, and another coin on the other side of the scale. Then he saw whether the two coins weigh equally, and if they don't, which one is heavier.

Write a programme that will, based on the weighing results, determine the type of coin for each coin for which it is possible to determine it uniquely.

Input Specification

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

Each of the following $V$ ~V~ lines contains the result of one weighing in the form of $ACB$ ~ACB~ where $A$ ~A~ and $B$ ~B~ are different integers less than or equal to $M$ ~M~, and $C$ ~C~ is the character = (equal) or < (less).

There is no space between the numbers and character $C$ ~C~. The result of one weighing tells us that Mirko's coin marked with $A$ ~A~ is of equal weight as the coin marked with $B$ ~B~ or lighter than it.

The weighing results won't be contradictory.

Output Specification

Output $M$ ~M~ lines. The $i^\text{th}$ ~i^\text{th}~ line must contain the type of coin marked with $i$ ~i~ – a sequence of characters of the form KX where $X$ ~X~ is an integer between $1$ ~1~ and $N$ ~N~.

If it isn't possible to uniquely determine the weight of the coin marked with $i$ ~i~, output the character ? in the $i^\text{th}$ ~i^\text{th}~ line.

Constraints

For all subtasks:

$2 \le N \le 300\,000$ ~2 \le N \le 300\,000~

$1 \le V \le 300\,000$ ~1 \le V \le 300\,000~

Subtask	Score	Constraints
$1$ ~1~	$10$ ~10~	$N = 2$ ~N = 2~, $1 \le M \le 1\,000$ ~1 \le M \le 1\,000~
$2$ ~2~	$40$ ~40~	$N = 2$ ~N = 2~, $1 \le M \le 300\,000$ ~1 \le M \le 300\,000~
$3$ ~3~	$10$ ~10~	$1 \le M \le 1\,000$ ~1 \le M \le 1\,000~
$4$ ~4~	$40$ ~40~	$1 \le M \le 300\,000$ ~1 \le M \le 300\,000~

Sample Input 1

Sample Output 1

K1
K2
?
K3
?

Sample Input 2

2 7 6
1=2
2=3
2=7
3<4
4=5
4=6

Sample Output 2

K1
K1
K1
K2
K2
K2
K1

Comments

There are no comments at the moment.