Strong Connected Components
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.
First line contains three integers n (2 ≤ n ≤ 3 *
105) , m and v (1 ≤ m, v ≤ 3 *
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.
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.
3 5 3 1<2 2<4 3=5
K1 K2 ? K3 ?
2 7 6 1=2 2=3 2=7 3<4 4=5 4=6
K1 K1 K1 K2 K2 K2 K1