Виявлення вірусів#10034

Виявлення вірусів

1 секунда

128 мегабайтів

Легка

На даний момент існує $n$ відомих науці видів вірусів. Кожен з цих вірусів має унікальну молекулярну масу, і їх можна позначити як $K_{1}, K_{2}, \dots, K_{n}$ K_1, K_2, \ldots, K_n у порядку зростання їх молекулярних мас.

Останнім часом Рафаель працює в лабораторії над виявленням нових видів вірусів. До лабораторії надійшло $m$ молекул певних вірусів. Рафаель проводить $v$ експериментів з цими вірусами. В результаті кожного експерименту, порівнюючи дві молекули вірусів, Рафаель визначає, чи вони рівні, чи одна з них має більшу молекулярну масу.

Допоможіть Рафаелю створити програму, яка на основі результатів експериментів визначить, до якого виду вірусів належить кожна з молекул. Якщо за наявними даними неможливо точно визначити вид молекули, виведіть символ '?' для цієї молекули.

Вхідні дані

У першому рядку задано три цілі числа $n$ ( $2 \leq n \leq 3 \cdot 1 0^{5}$ 2 \le n \le 3 \cdot 10^5), $m$ і $v$ ( $1 \leq m, v \leq 3 \cdot 1 0^{5}$ 1 \le m, v \le 3 \cdot 10^5). На наступних $v$ рядках наведено результати експериментів у форматі $A C B$ . Тут $A$ і $B$ — це цілі числа, що представляють порядкові номери порівнюваних молекул, а $C$ — один із символів '=', '<', '>'. Між числами $A$ , $B$ і символом $C$ немає пробілів. Гарантується, що серед експериментів немає суперечностей.

Вихідні дані

Виведіть $m$ рядків. У $i$ -му рядку виведіть один із символів ( $K_{1}, K_{2}, \dots, K_{n}$ K_1, K_2, \ldots, K_n), якщо можна точно визначити вид $i$ -ї молекули, інакше символ '?'.

Приклади

Приклад 1

Приклад 2