Групи 1
Групи 1
В Житоленді у дітей забрали телефони і тепер вони почали шукати друзів (всі діти забули інших дітей взагалі і ніхто не з ким не дружить).
В місті проживае n
дітей (ім'я i
-тої дитини - "i").
Спочатку кожна людина - це група.
Дано масив a
(розміром n
), ai
- впливовість дитини "i".
Акіа та Гульнар попросили вас допомогти їм визначити яка група має найбільшу впливовість - вони зададуть вам q
запитів.
Запити бувають двох типів:
1 i j
- Яка з груп впливовіша? Та, в якій знаходиться дитинаi
(в цьому випадку вивести ">") чи та, в якій знаходитьсяj
(в цьому випадку вивести "<"). Якщо вони в одній групі або групи мають однакову впливовість то вивести "=".2 i j
- Група в якій знаходится дитинаі
і група в якій знаходится дитинаj
об'едналися. Якщо вони в одній групі, то нічого робити не потрібно.
Впливовість нової групи - це сума впливу груп в яких знаходится діти "і" і "j".
Вхідні данні
У першому рядку записано числа n та q.(1 ≤ n, q ≤ 2*105
)
У наступному рядку знаходиться масив a (1 ≤ ai ≤ 109
)
У наступних 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
>=><