Cho một cây gồm ~n~ đỉnh, ban đầu có gốc tại đỉnh ~1~, mỗi đỉnh mang một số nguyên.

Có ~q~ truy vấn, mỗi truy vấn thuộc một trong ba loại sau:

1. ~1~ ~u~ — đổi gốc của cây thành đỉnh ~u~.
2. ~2~ ~u~ ~v~ ~x~ — cộng ~x~ vào mọi đỉnh thuộc cây con nhỏ nhất chứa cả hai đỉnh ~u~ và ~v~.
3. ~3~ ~u~ — tính tổng giá trị của mọi đỉnh trong cây con gốc ~u~.

Các cây con ở truy vấn loại ~2~ và ~3~ được xét theo gốc hiện tại của cây.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên ~n~, ~q~.
• Dòng thứ hai chứa ~n~ số nguyên — giá trị ban đầu trên các đỉnh.
• ~n - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u~, ~v~ — có một cạnh nối ~u~ và ~v~.
• ~q~ dòng tiếp theo chứa các truy vấn theo định dạng đã nêu.

Kết quả

Với mỗi truy vấn loại ~3~, in ra đáp án trên một dòng.

Ví dụ

Đầu vào:

4 6
4 3 5 6
1 2
2 3
3 4
1 3
2 2 4 3
3 3
1 1
2 2 4 -3
3 2

Đầu ra:

30
14

Giải thích: Sau khi đổi gốc thành đỉnh ~3~, cây con nhỏ nhất chứa cả ~2~ và ~4~ là toàn bộ cây, nên mọi đỉnh được cộng ~3~ — tổng cây con gốc ~3~ (cả cây) là ~7 + 6 + 8 + 9 = 30~. Sau khi đổi gốc về đỉnh ~1~, cây con nhỏ nhất chứa ~2~ và ~4~ là cây con gốc ~2~, được cộng ~-3~; tổng cây con gốc ~2~ khi đó là ~3 + 5 + 6 = 14~.

Giới hạn

• ~1 \le n, q \le 10^5~
• ~1 \le u, v \le n~
• ~|x| \le 10^6~
• Giá trị tuyệt đối của các số trên đỉnh không vượt quá ~10^6~.