Sau khi chia ngân khố thành công, Bờm tiếp tục cuộc hành trình đến một vùng biển rộng lớn, nơi có ~n~ hòn đảo biệt lập. Trước đây, người dân di chuyển giữa các đảo bằng tàu thuyền, nhưng điều đó bây giờ không còn thuận tiện nữa. Chính quyền địa phương quyết định xây dựng một hệ thống cầu nối để giúp việc đi lại giữa các đảo trở nên dễ dàng hơn.

Tuy nhiên, thay vì xây dựng ngay lập tức, họ muốn thực hiện một số giả định thử nghiệm trước khi thi công thực tế. Và một lần nữa, Bờm được giao trọng trách quan trọng này.

Trong mô hình thử nghiệm mỗi hòn đảo được xem là một đỉnh trong đồ thị, mỗi cây cầu sẽ là một cạnh có trọng số là độ dài của cây cầu. Ban đầu chưa có cây cầu nào, chính quyền sẽ liên tục đưa ra các truy vấn để thử nghiệm việc xây cầu và kiểm tra khoảng cách giữa các đảo.

Bờm cần giúp chính quyền thực hiện ~Q~ truy vấn, mỗi truy vấn thuộc một trong hai loại:

1. Xây dựng cầu giả định: Cho trước hai đảo ~u~ và ~v~, chính quyền muốn thử nghiệm việc xây một cây cầu có độ dài ~w~ giữa hai đảo này. Tuy nhiên, hệ thống cầu phải đảm bảo không có chu trình.
2. Tính khoảng cách di chuyển: Người dân muốn biết độ dài ngắn nhất khi di chuyển giữa hai đảo ~u~ và ~v~. Nếu hai đảo này chưa được nối với nhau bằng cầu, thì câu trả lời là -1.

Yêu cầu: Hãy thực hiện các truy vấn và đưa ra câu trả lời cho các truy vấn loại 2.

Input

• Dòng đầu tiên là hai số nguyên dương ~n, Q~ (~1 \le n, Q \le 2 \times 10^5~) tương ứng là số lượng hòn đảo và số lượng truy vấn.
• ~Q~ dòng sau thể hiện các truy vấn có thể loại 1 hoặc loại 2.

Output

• Ghi ra các câu trả lời cho các truy vấn loại 2 theo thứ tự của nó trong file input.

Sample Input 1

5 8
1 1 2 5
1 3 5 7
2 2 4
1 5 4 1
2 3 4
1 1 5 6
2 1 4
2 2 4

Sample Output 1

-1
8
7
12