Sau khi đã trải qua những áp lực, mệt mỏi trong cuộc sống, Mạnh đã dần tập chơi cây cảnh Bonsai để giải stress sau một ngày dài căng thẳng. Mỗi chậu cây Bonsai của Mạnh, anh ấy đều rất chăm chút và dán những con số đặc biệt lên các nhánh cây để lưu giữ các kỷ niệm với nó.

Hôm nay, Mạnh đã đem một chậu câu Bonsai lên CLB Lập Trình H3.2 để khoe với Lab. Thế những khi nhìn qua chậu cây Bonsai, thầy Tình đã nhận ra đây rất giống với chậu cây được mua ngoài tiệm nên chính vì thế thầy Tình đã đặt ra cho Mạnh các truy vấn để chứng thực xem cây Bonsai này có thật sự là do Mạnh chăm sóc hay không.

Cụ thể, chậu Bonsai của Mạnh được mô phỏng lại thành một cây có ~N~ đỉnh và tương ứng với ~N - 1~ cạnh mỗi cạnh sẽ có một trọng số ~W~ (là con số đặc biệt mà Mạnh đã dán lên). Thầy Tình sẽ truy vấn Mạnh ~Q~ câu hỏi, với mỗi câu hỏi sẽ là một trong 2 dạng:

1. Thầy Tình sẽ thay đổi giá trị trọng số của cạnh thứ ~m~ thành ~X~. Để tránh trường hợp Mạnh có thể đã học thuộc lòng các câu hỏi mà thầy Tình có thể hỏi.
2. Thầy Tình sẽ hỏi Mạnh kết quả khi XOR các giá trị trọng số trên đường đi từ ~u~ đến ~v~ là bao nhiêu?

Do đã quá mệt mỏi với việc học tập (hoặc có thể là do chậu Bonsai này không phải anh ấy tự trồng) nên anh ấy đã nhờ bạn đứng cạnh và nhắc anh ấy câu trả lời khi thầy Tình truy vấn. Bạn hãy làm một người tốt và giúp đỡ Mạnh nhé!

Input

Dòng đầu tiên chứa hai số nguyên ~N, Q~ ~(1 \leq N, Q \leq 100000)~ tương ứng với số đỉnh mô phỏng cây Bonsai và số truy vấn của* thầy Tình* đặt ra.

~N - 1~ dòng tiếp theo, mỗi dòng sẽ chứa ba số nguyên ~u, v, W~ ~(1 \leq u, v \leq N, 1 \leq W \leq 10^9)~ tương ứng với cạnh ~u, v~ sẽ có trọng số là ~W~.

~Q~ dòng tiếp theo, đầu tiên sẽ chứa số nguyên ~type~ ~(1 \leq type \leq 2)~ nếu:

• ~type = 1~, thì sẽ chứa tiếp theo hai số nguyên ~m, X~ ~(1 \leq m \leq N - 1, 1 \leq X \leq 10^9)~ tương ứng với truy vấn ~1~ của thầy Tình.
• ~type = 2~, thì sẽ chứa tiếp theo hai số nguyên ~u, v~ ~(1 \leq u, v \leq N)~ tương ứng với truy vấn ~2~ của thầy Tình.

Output

Với truy vấn ~2~ bạn hãy nhắc Mạnh kết quả của truy vấn tương ứng nhé.

Sample Input

5 3
1 2 2
1 3 3
2 4 5
3 5 7
2 4 5
1 1 9
2 4 5

Sample Output

3
8