e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Змагання

Strong Connected Components

Обнаружение вирусов

На данный момент, всего есть n видов вирусов, известных науке. Каждый из этих вирусов обладает различной молекулярной массой и их можно обозначить как K1, K2, ... , Kn в порядке возрастания их молекулярных масс.

В последние дни, Рафаэль занимается в лаборатории обнаружением новых видов вирусов. В лабораторию было доставлено m молекул каких-то вирусов. Рафаэль проводит v вычислений на этих вирусах. В результате каждого вычисления, взвешивая две молекулы вирусов, Рафаэль приходит к выводу, что они, либо равны, либо одна из них больше другой по молекулярной массе.

Помогите Рафаэлю написать программу, которая на основании вычислений определит, к какому виду вирусов принадлежит каждая из молекул. Если, по имеющимся данным, невозможно точно определить вид молекулы, то напечатайте символ '?' в соответствии с этой молекулой.

Входные данные

В первой строке заданы три целых числа n (2n3 *105) , m и v (1m, v3 * 105) . На следующих v строках задаются результаты вычислений в виде строки формата ACB. Здесь, A и B являются целыми числами - порядковыми номерами сравниваемых молекул, а C является одним из символов '=', '<', '>'. Между числами A, B и символом C нет пробелов. Гарантируется, что среди вычислений нету нестыковок.

Выходные данные

Выведите m строк. В i-ой строке выведите один из символов (K1, K2, ... , Kn), если можно точно определить вид i-ой молекулы, иначе символ '?'.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
3 5 3
1<2
2<4
3=5
Вихідні дані #1
K1
K2
?
K3
?
Вхідні дані #2
2 7 6
1=2
2=3
2=7
3<4
4=5
4=6
Вихідні дані #2
K1
K1
K1
K2
K2
K2
K1
Джерело 2019-2020 Азербайджан. Финал Республиканской олимпиады, 17 июня.