Problems
Disjoint Sets Union 2
Disjoint Sets Union 2
Implement disjoint sets union data structure. You have to perform queries of two types:
\begin{itemize}
\item \textbf{union u v} --- unite two sets that contain $u$ and $v$, respectively;
\item \textbf{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.
\end{itemize}
\InputFile
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 \textbf{union} the line looks like \textbf{union u v} $~(1 \le u, v \le n)$.
For a query \textbf{get} the line looks like \textbf{get v} $~(1 \le v \le n)$.
\OutputFile
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.
Input example #1
5 11 union 1 2 get 3 get 2 union 2 3 get 2 union 1 3 get 5 union 4 5 get 5 union 4 1 get 5
Output example #1
3 3 1 1 2 2 1 3 3 5 5 1 4 5 2 1 5 5