Cho một đồ thị cây gồm ~n~ đỉnh, các đỉnh được đánh số thứ tự từ 1 tới ~n~. Có ~n - 1~ cạnh kết nối các đỉnh của cây, cạnh thứ ~i~ nối hai đỉnh ~a_i~ với ~b_i~ và có độ dài ~w_i~. Ban đầu tất cả các đỉnh của cây được tô màu xanh.

Có ~q~ truy vấn, mỗi truy vấn thuộc 1 trong ba dạng:

1. Từ một đỉnh ~s~, cần cho biết độ dài đường đi ngắn nhất để tới được đỉnh màu đỏ;
2. Đổi màu một đỉnh ~u~ của cây: nếu đang màu xanh thì đổi sang đỏ, nếu đang đỏ đổi sang xanh;
3. Thay đổi độ dài một cạnh của cây.

Yêu cầu: Thực hiện các truy vấn trên cây.

Input

• Dòng đầu ghi số nguyên ~n, q~ (~2 \le n \le 10^5, 1 \le q \le 10^5~);
• ~n - 1~ dòng tiếp theo, mỗi dòng chứa 3 số nguyên ~a_i, b_i, w_i~ (~1 \le a_i, b_i \le n, 0 \le w_i \le 10^9~) mô tả 1 cạnh của cây;
• ~q~ dòng tiếp theo, mỗi dòng mô tả một truy vấn:
  • Truy vấn loại 1 chứa 2 số nguyên ~1~ và ~s~ (~1 \le s \le n~);
  • Truy vấn loại 2 chứa 2 số nguyên ~2~ và ~u~ (~1 \le u \le n~);
  • Truy vấn loại 3 chứa 4 số nguyên ~3, a_i, b_i, w_i~ (~1 \le a_i, b_i \le n, 0 \le w_i \le 10^9~): cạnh nối 2 đỉnh ~a_i~ và ~b_i~ có độ dài mới là ~w_i~ (dữ liệu đảm bảo cạnh nối là tồn tại).

Output

• Với mỗi truy vấn loại 1 đưa ra 1 số nguyên là đáp án cần tìm. Nếu không thể đi tới đỉnh màu đỏ thì ghi ~-1~.