Группы 1
Группы 1
В Житолендии у детей забрали телефоны и теперь они начали искать друзей (все дети забыли других детей вообще и никто не с кем не дружит).
В городе проживает n
детей (имя i-ного ребенка - "i").
Сначала каждый человек - это группа.
Дан массив a (размером n), ai
- влиятельность ребенка "i".
Акиа и Гульнар попросили вас помочь им определить какая группа имеет наибольшую влиятельность - они зададут вам q
запросов.
Запросы бывают двух типов:
1 i j
- Какая из групп более влиятельная? Та, в которой находится ребенок i (в этом случае вывести ">") или та, в которой находится j (в этом случае вывести "<"). Если они в одной группе или группы имеют одинаковую влиятельность то вывести "=".2 i j
- Группа в которой находится ребенокi
и группа в которой находится ребенокj
объединились. Если они в одной группе, то ничего делать не нужно.
Влиятельность новой группы - это сумма влияния групп в которых находится дети "i" и "j".
Выходные данные
В первой строке записано число n
и q
. ( 1 ≤ n, q ≤ 2 * 10 ^ 5
)
В следующей строке находится массив a (1 ≤ a [i] ≤ 10 ^ 9
)
В следующих q
строках записаны запросы.
Выходные данные
Вывести ответы на запросы типа 1.
10 6 1 1 1 1 1 1 1 3 1 10 1 10 1 1 1 2 2 1 2 1 1 3 2 3 5 1 5 10
>=><