Tại thời nhà \(\texttt{Minh(明)}\), nhà vua p2o2HuaGiaBao nhận thấy mỗi người dân có rất nhiều mối quan hệ. Có những người có \(3\) đời dòng họ thậm chí tận \(9\) đến \(10\) dòng họ.

Để tiện quản lý, nhà vua yêu cầu sau khi sinh xong một đứa con cần đến cơ quan để đăng kí vào Cây Gia Phả để có thể thực hiện \(\text{Tru di tam/cửu tộc (灭族三代或九代)}\) khi vi phạm pháp luật một cách triệt để. Nhà vua p2o2HuaGiaBao muốn thực hiện một số thao tác trên các Cây Gia Phả để rèn luyện tư duy cho các thái giám (PhuocThien, uou). Hoàng tử trongphithien nói rằng:

Nếu ai không giải được bài toán của đức vua sẽ bị đuổi vĩnh viễn khỏi danh sách thái giám trong hoàng cung.

Thật vậy, không ai giải được bài toán này nên vì lượng test case lớn và bài toán quá khó với họ nên nhờ các coder tài năng tương lai đến giúp họ. Bài toán khó nhằn ấy như sau:

Xét một một mạng lưới mối quan hệ dạng cây (Relationship Tree) gồm \(n\) thành viên được đánh số từ \(1\) đến \(n\). Mỗi thành viên \(i\) ban đầu sở hữu một chỉ số ảnh hưởng là \(val_i\). Có \(q\) truy vấn thuộc \(3\) loại sau:

• Loại \(1\) (1 u c x mod): Thực hiện một chiến dịch truyền thông từ người đứng đầu nhóm \(u\). Tất cả các thành viên thuộc cây con gốc \(u\) (nhóm do \(u\) quản lý) được tăng chỉ số ảnh hưởng thêm một lượng bằng: \(\lfloor (c \times x) / mod \rfloor\).
• Loại \(2\) (2 u v c): Cần thiết lập một cầu nối liên lạc ngắn nhất từ thành viên \(u\) đến thành viên \(v\). Hãy tính tổng chỉ số ảnh hưởng của tất cả các thành viên nằm trên lộ trình kết nối này, sau đó cộng thêm một chi phí phát sinh là \(c\).
• Loại \(3\) (3 u p1 p2 p3): Tìm trọng tâm (Centroid) của cây con gốc \(u\) (nhóm do \(u\) quản lý). Trọng tâm là thành viên mà nếu ta chọn người đó làm đại diện điều hành nhóm, thì không có một nhánh cấp dưới trực thuộc nào (xét riêng trong phạm vi cây con gốc \(u\)) chiếm quá một nửa tổng số thành viên của cả nhóm. Ba tham số \(p_1, p_2, p_3\) là các mã bảo mật hệ thống (nhiễu dữ liệu) cần được đọc vào nhưng không ảnh hưởng đến vị trí trọng tâm.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) (\(1 \le n, q \le 250000\)) — tương ứng là số lượng đỉnh của cây và số lượng câu hỏi truy vấn.
• Dòng thứ hai chứa \(n\) số nguyên cách nhau bởi khoảng trắng \(val_1, val_2, \dots, val_n\) (\(1 \le val_i \le 10^9\)) — biểu diễn mức năng lượng ảnh hưởng ban đầu của từng đỉnh từ \(1\) đến \(n\).
• \(n - 1\) dòng tiếp theo: Mỗi dòng chứa hai số nguyên \(u\) và \(v\) (\(1 \le u, v \le n, u \ne v\)) — mô tả một cạnh nối không hướng giữa đỉnh \(u\) và đỉnh \(v\) trên cây. Dữ liệu bảo đảm các cạnh tạo thành một cấu trúc cây liên thông hợp lệ.
• \(q\) dòng cuối cùng: Mỗi dòng mô tả một truy vấn thuộc một trong ba dạng sau:
  • Truy vấn loại \(1\): 1 u c x mod với \(1 \le u \le n\) và \(1 \le c, x, mod \le 1000\).
  • Truy vấn loại \(2\): 2 u v c với \(1 \le u, v \le n\) và \(0 \le c \le 10^6\).
  • Truy vấn loại \(3\): 3 u p1 p2 p3 với \(1 \le u \le n\) và \(1 \le p_1, p_2, p_3 \le 1000\) (các tham số nhiễu).

Output

• Với mỗi truy vấn loại \(2\) hoặc loại \(3\), in ra kết quả tính toán được trên một dòng riêng biệt theo đúng thứ tự xuất hiện của chúng trong file dữ liệu đầu vào.
• Kết quả của truy vấn loại \(2\) là một số nguyên duy nhất.
• Kết quả của truy vấn loại \(3\) là một số nguyên duy nhất chỉ số của đỉnh đóng vai trò là trọng tâm của cây con đó. Nếu có nhiều trọng tâm hợp lệ, thí sinh có thể in ra bất kỳ đỉnh nào thỏa mãn tính chất. Đề bài đảm bải truy vấn có lời giải.

Example

5 4
10 20 30 40 50
1 2
1 3
2 4
2 5
1 2 5 10 2
2 4 5 15
3 2 100 200 300
2 1 3 0

200
2
40

4 3
5 5 5 5
1 2
2 3
3 4
1 2 10 10 3
3 1 9 9 9
2 1 4 100

2
219