Cho một đồ thị gồm ~n~ đỉnh, ban đầu đồ thị không có cạnh nào. Trong đó, đỉnh thứ ~i~ có giá trị là ~i~.

Cho ~m~ truy vấn, mỗi truy vấn thuộc một trong hai loại sau:

• union ~u~ ~v~ (~1 \leq u, v \leq n~) — Nối một cạnh giữa hai đỉnh ~u~ và ~v~.

• get ~u~ (~1 \leq u \leq n~) — Trong thành phần chứa đỉnh ~u~, tìm giá trị đỉnh bé nhất, giá trị đỉnh lớn nhất và số lượng đỉnh của thành phần liên thông.

Input

Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~m~ (~1 \leq n, m \leq 3 \times 10^5~) — Là số đỉnh của đồ thị và số truy vấn.

Trong ~m~ dòng tiếp theo, mỗi dòng là một loại truy vấn thuộc một trong hai loại trên.

Output

Với mỗi thao tác loại get, hãy in ra 3 số nguyên dương trên từng dòng. Thứ tự in của 3 số nguyên dương trên mỗi dòng lần lượt là: giá trị đỉnh bé nhất, giá trị đỉnh lớn nhất và số lượng đỉnh của thành phần liên thông.

Scoring

Sample Input 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

Sample Output 1

3 3 1
1 2 2
1 3 3
5 5 1
4 5 2
1 5 5