/\             /\             /\
              /  \           /  \           /  \
             /    \         /    \         /    \
            /      \       /      \       /      \
        ___/________\_____/________\_____/________\___
       |                                              |
       |   [ TRINIDAD ]    [ CONCEPCION ]  [ VICTORIA ]
       |______________________________________________|
                       \              /
    ~~~~~~~~~~~~~~~~~~~~\~~~~~~~~~~~~/~~~~~~~~~~~~~~~~~~~~
      ~      ~     ~     \  (Tử Địa) /    ~     ~      ~
         ~      ~         \_________/         ~      ~

Bình minh ngày 27 tháng 4 năm 1521, eo biển Mactan rực lửa.
Họ đông như kiến, tiếng gầm rú của họ làm rung chuyển cả mặt nước bẩn thỉu. Khi đại bác của chúng ta câm lặng ngoài khơi vì mắc cạn, tôi biết lưỡi hái của tử thần đã chạm đến cổ.
— Trích hồi ký của Antonio Pigafetta, thư ký đoàn viễn chinh.

Lời cảnh báo của Raja Humabon về sự nguy hiểm của tộc trưởng Lapulapu đã bị Ferdinand Magellan gạt đi trong sự kiêu ngạo tột cùng. Magellan tin rằng giáp sắt Toledo và súng hỏa mai Tây Ban Nha có thể đè bẹp bất kỳ thế lực bản địa nào. Nhưng eo biển Mactan không phải là một bãi chiến trường thông thường; đó là một tử địa san hô. Thủy triều rút nhanh một cách kỳ lạ vào rạng sáng đã bỏ lại các chiến hạm viễn chinh khổng lồ nằm phơi bụng cách bờ hơn một dặm. Pháo hạm hoàn toàn bất lực.

Dưới làn mưa lao tre tẩm độc và đá nhọn trút xuống từ các bụi rậm ngập mặn, Magellan đã ngã xuống sau khi bị một mũi tên độc găm trúng chân trái. Cái chết của vị tổng tư lệnh vĩ đại khiến hạm đội Tây Ban Nha rơi vào hoảng loạn cực độ. Quyền chỉ huy tạm thời được trao lại cho Duarte Barbosa và João Serrão. Để bảo toàn những thủy thủ còn sống sót trên 3 con tàu Trinidad, Concepcion và Victoria, họ buộc phải thiết lập một phòng tuyến rút lui chiến lược xuyên qua cụm \(N\) đảo đá và bãi cát ngầm quanh eo biển Mactan.

Do đặc thù địa hình luồng lạch vô cùng phức tạp, \(N\) hòn đảo này được kết nối với nhau bởi đúng \(N-1\) tuyến đường biển tự nhiên đã được vẽ bản đồ an toàn. Hệ thống này kết nối toàn bộ các đảo và không hề tồn tại chu trình (bất kỳ đường vòng nào khác đều có nguy cơ đâm vào rạn san hô ngầm sắc nhọn làm đắm tàu). Mạng lưới này tạo thành một cấu trúc cây (Tree) với hòn đảo gốc số \(1\) là nơi soái hạm Trinidad đang neo đậu để điều phối toàn bộ lực lượng. Mỗi đảo \(i\) ban đầu được bố trí một mức độ phòng thủ bằng các công sự gỗ là \(A_i\).

Để đối phó với sự bao vây thần tốc từ hàng trăm thuyền độc mộc Balangay cực kỳ cơ động của chiến binh Lapulapu, Duarte Barbosa cần liên tục điều phối lực lượng thông qua hai mệnh lệnh quân sự khẩn cấp:

1. Hành lang chi viện: Nhận được tin báo về hướng hành quân của quân bộ tộc, một đội thuyền tuần tra tốc độ cao mang theo các tấm khiên Toledo hạng nặng được phái đi càn quét dọc theo con đường độc đạo nối liền hai đảo \(u\) và \(v\). Tất cả các đảo nằm trên đường đi từ \(u\) tới \(v\) (bao gồm cả \(u\) và \(v\)) sẽ được gia cố thêm một lượng sức mạnh quân sự là \(X\) (nếu \(X\) âm, điều đó có nghĩa là rút bớt quân để chi viện nơi khác).
2. Thanh tra phân khu: Trước khi hạ lệnh rút neo toàn bộ hạm đội ra khơi xa, bộ chỉ huy cần kiểm tra khả năng phòng thủ tổng thể của một phân khu quân sự chịu sự quản lý của đảo tiền tiêu \(u\). Bạn phải lập tức báo cáo mức độ phòng thủ lớn nhất của một hòn đảo bất kỳ nằm trong cây con (subtree) có gốc tại \(u\).

Hãy giúp các thủy thủ Tây Ban Nha giữ vững phòng tuyến và hoàn thành cuộc rút lui lịch sử này!

Nhiệm vụ

• Cho một cây gồm \(N\) đỉnh được đánh số từ \(1\) đến \(N\), gốc tại đỉnh \(1\). Đỉnh \(i\) có giá trị ban đầu là \(A_i\).
• Có \(Q\) truy vấn thuộc hai loại:
  • 1 u v x: Cộng thêm giá trị \(x\) vào tất cả các đỉnh trên đường đi đơn giữa hai đỉnh \(u\) và \(v\) (bao gồm cả \(u\) và \(v\)).
  • 2 u: Tìm giá trị lớn nhất trong số các đỉnh thuộc cây con gốc \(u\).

Input

• Dòng thứ nhất gồm hai số nguyên \(N\) và \(Q\) (\(1 \le N, Q \le 10^5\)).
• Dòng thứ hai gồm \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(-10^9 \le A_i \le 10^9\)).
• \(N - 1\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(u\) và \(v\) mô tả một tuyến đường biển nối trực tiếp hai đảo \(u\) và \(v\).
• Q dòng tiếp theo, mỗi dòng mô tả một truy vấn theo định dạng:
  • 1 u v x (\(-10^9 \le x \le 10^9\))
  • 2 u

Output

• Với mỗi truy vấn loại 2, in ra giá trị lớn nhất tìm được trên một dòng.

Example

5 4
1 2 3 4 5
1 2
1 3
2 4
2 5
2 2
1 4 3 10
2 2
2 1

5
14
14

        [1] (A=1)
       / \
  [2] (A=2) [3] (A=3)
   / \
[4] (A=4) [5] (A=5)

3 3
5 10 15
1 2
2 3
2 1
1 1 3 -5
2 1

15
10

Scoring

• Subtask 1 (\(30\%\) số điểm): \(N, Q \le 10^5\) và cây có dạng một đường thẳng (Đỉnh \(i\) chỉ nối với \(i+1\))
• Subtask 2 (\(70\%\) số điểm): Không có ràng buộc gì thêm