e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

Strong Connected Components

Virus detection

At the moment, there are n types of viruses known to science. Each of these viruses has a different molecular weight and can be designated as K1, K2, ..., Kn in increasing order of their molecular weights.

In recent days, Raphael has been researching new types of viruses in the laboratory. m molecules of some viruses were delivered to the laboratory. Raphael performs v calculations on these viruses. As a result of each calculation, weighing two molecules of viruses, Raphael concludes that they are either equal or one of them is larger than the other in molecular weight.

Help Raphael to write a program that, based on calculations, determines which type of virus each molecule belongs to. If, according to the available data, it is impossible to determine the exact type of molecule, then type the symbol '?' in accordance with this molecule.

Input

First line contains three integers n (2n3 *105) , m and v (1m, v3 * 105). The following v lines specify the calculation results in the string of type ACB. Here A and B are integers - the sequence numbers of the compared molecules, C is one of the symbols '=', '<', '>'. Between numbers A, B and symbol C there is no spaces. It is guaranteed that among the calculations there are no inconsistencies.

Output

Print m lines. Print in the i-th line one of symbols (K1, K2, ... , Kn) if its possible to determine the type of the i-th molecule, and symbol '?' otherwise.

Time limit 1 second
Memory limit 128 MiB
Input example #1
3 5 3
1<2
2<4
3=5
Output example #1
K1
K2
?
K3
?
Input example #2
2 7 6
1=2
2=3
2=7
3<4
4=5
4=6
Output example #2
K1
K1
K1
K2
K2
K2
K1
Source 2019-2020 Azerbaijan Final, June 17.