Disjoint Sets Union 2

Implement disjoint sets union data structure. You have to perform queries of two types:

• union u v — unite two sets that contain $u$ and $v$, respectively;

• get v — find the set to which $v$ belongs to, find the minimal and the maximal element of the set, and the total number of elements in it.

Input

The first line contains two integers $n$ and $m(1\le n,m\le 3\cdot 10^5)$ — the number of elements and the number of queries. Next $m$ lines contain queries, one per line.

For a query union the line looks like union u v $(1\le u,v\le n)$.

For a query get the line looks like get v $(1\le v\le n)$.

Output

For each operation get you should output the result on a separate line in the respected order. Each result should consist of three integers: the minimal element, the maximal element, and the number of elements in the set.

Examples