Виявлення вірусів
На даний момент існує 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-ї молекули, інакше символ '?'.