Обнаружение вирусов
На данный момент, всего есть n видов вирусов, известных науке. Каждый из этих вирусов обладает различной молекулярной массой и их можно обозначить как K1, K2, ... , Kn в порядке возрастания их молекулярных масс.
В последние дни, Рафаэль занимается в лаборатории обнаружением новых видов вирусов. В лабораторию было доставлено m молекул каких-то вирусов. Рафаэль проводит v вычислений на этих вирусах. В результате каждого вычисления, взвешивая две молекулы вирусов, Рафаэль приходит к выводу, что они, либо равны, либо одна из них больше другой по молекулярной массе.
Помогите Рафаэлю написать программу, которая на основании вычислений определит, к какому виду вирусов принадлежит каждая из молекул. Если, по имеющимся данным, невозможно точно определить вид молекулы, то напечатайте символ '?' в соответствии с этой молекулой.
Входные данные
В первой строке заданы три целых числа n (2 ≤ n ≤ 3 *10^5) , m и v (1 ≤ m, v ≤ 3 * 10^5) . На следующих v строках задаются результаты вычислений в виде строки формата ACB. Здесь, A и B являются целыми числами - порядковыми номерами сравниваемых молекул, а C является одним из символов '=', '<', '>'. Между числами A, B и символом C нет пробелов. Гарантируется, что среди вычислений нету нестыковок.
Выходные данные
Выведите m строк. В i-ой строке выведите один из символов (K1, K2, ... , Kn), если можно точно определить вид i-ой молекулы, иначе символ '?'.