Cây Đũa Phép Cơm Nguội

Trong thế giới phù thủy, có $N$ phù thủy, mỗi người sở hữu một lượng sức mạnh phép thuật $p_i$. Các phù thủy có thể tạo ra liên kết thần phục - những kết nối ma thuật cho phép sức mạnh truyền qua giữa họ.

Cây Đũa Phép Cơm Nguội (Elder Wand), một bảo vật huyền thoại, có khả năng khuếch đại sức mạnh phép thuật truyền qua các chuỗi thần phục. Khi một phù thủy cầm Cây Đũa Phép và truyền sức mạnh đến một phù thủy khác qua chuỗi liên kết, tổng sức mạnh được khuếch đại bằng tổng sức mạnh của tất cả phù thủy trên đường đi (bao gồm cả hai đầu).

Ban đầu, không có liên kết thần phục nào tồn tại. Bạn cần xử lý $Q$ thao tác:

• 1 u v - Tạo liên kết thần phục giữa phù thủy $u$ và phù thủy $v$. Đảm bảo $u$ và $v$ thuộc hai nhóm khác nhau.
• 2 u v - Phá hủy liên kết trực tiếp giữa phù thủy $u$ và $v$. Đảm bảo liên kết này tồn tại.
• 3 u v - Tính tổng sức mạnh trên đường đi từ phù thủy $u$ đến phù thủy $v$. Đảm bảo $u$ và $v$ thuộc cùng một nhóm.
• 4 u x - Sức mạnh của phù thủy $u$ thay đổi thành $x$.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $N$ và $Q$.
• Dòng thứ hai chứa $N$ số nguyên $p_1,p_2,\dots ,p_N$ - sức mạnh ban đầu của các phù thủy.
• $Q$ dòng tiếp theo, mỗi dòng mô tả một thao tác theo định dạng trên.

Dữ liệu ra

Với mỗi thao tác loại 3, in ra tổng sức mạnh trên đường đi trên một dòng.

Ràng buộc

• $1\le N,Q\le {10}^5$
• $1\le p_i,x\le {10}^9$
• $1\le u,v\le N$
• Các thao tác luôn hợp lệ (xem mô tả ở trên)
• Tổng sức mạnh trên đường đi có thể vượt quá $2^{31}-1$

Ví dụ