Mùa hè năm 1944, khi Chiến tranh thế giới thứ hai bước vào giai đoạn quyết liệt, Hồng quân Liên Xô mở cuộc tấn công quy mô lớn nhằm đẩy lùi quân đội Đức Quốc xã khỏi lãnh thổ Belarus. Chiến dịch mang mật danh Bagration, được đặt theo tên vị tướng Nga Pyotr Bagration, bắt đầu vào ngày 22/6/1944, đúng ba năm sau khi Đức phát động cuộc xâm lược Liên Xô.

Mục tiêu chính của chiến dịch là tiêu diệt Cụm tập đoàn quân Trung tâm của Đức, giải phóng Belarus và mở đường tiến về phía tây. Liên Xô huy động một lực lượng khổng lồ gồm hàng triệu binh sĩ, hàng nghìn xe tăng, pháo binh và máy bay, tổ chức các đợt tấn công đồng loạt trên nhiều hướng nhằm chia cắt và bao vây các đơn vị Đức. Nhờ sự phối hợp giữa các phương diện quân, những tuyến phòng thủ của quân Đức nhanh chóng bị xuyên thủng, khiến lực lượng phòng thủ gặp nhiều khó khăn trong việc tổ chức phản công.

Trong những tuần đầu tiên, Hồng quân lần lượt giải phóng nhiều thành phố chiến lược như Vitebsk, Orsha, Mogilev và Minsk. Đặc biệt, Minsk được giải phóng vào ngày 3/7/1944, đánh dấu một thắng lợi quan trọng của chiến dịch. Quân Đức chịu tổn thất rất nặng nề, nhiều đơn vị bị bao vây và tiêu diệt, hệ thống phòng thủ tại Belarus gần như sụp đổ. Đà tiến công của Liên Xô tiếp tục mở rộng về phía tây, hướng đến Ba Lan và biên giới Đông Phổ.

Đến cuối tháng 8/1944, Chiến dịch Bagration đã đạt được phần lớn các mục tiêu chiến lược đề ra. Quân đội Liên Xô giải phóng phần lớn Belarus, đẩy lùi quân Đức trên một mặt trận rộng lớn và làm suy yếu nghiêm trọng khả năng phòng thủ của Đức Quốc xã ở phía đông. Chiến thắng này không chỉ tạo điều kiện cho Hồng quân tiếp tục tiến vào Đông Âu mà còn góp phần đẩy nhanh quá trình sụp đổ của Đức Quốc xã trong Chiến tranh thế giới thứ hai.

Chiến dịch Bagration được xem là một trong những chiến dịch quân sự lớn nhất và có ảnh hưởng sâu rộng nhất trên Mặt trận phía Đông. Cũng giống như Trận Ardennes ở mặt trận phía tây vào cuối năm 1944, chiến dịch này cho thấy tầm quan trọng của việc tổ chức lực lượng, phối hợp các hướng tấn công và tận dụng những điểm yếu trong hệ thống phòng thủ của đối phương. Tuy nhiên, trong khi Trận Ardennes là cuộc phản công lớn cuối cùng của Đức ở phía tây, Chiến dịch Bagration lại là đòn tiến công quyết định của Liên Xô, góp phần thay đổi cục diện chiến tranh và đưa Hồng quân tiến gần hơn đến Berlin.

Yêu cầu

• Bộ chỉ huy cần xử lý \(Q\) yêu cầu theo thứ tự xuất hiện. Các yêu cầu bao gồm cập nhật tình hình chiến trường và đánh giá hiệu quả của những tuyến hành quân.

  • Loại 1: Cập nhật giá trị chiến lược của một thành phố.
  • Loại 2: Cập nhật chi phí hành quân của một tuyến đường nối trực tiếp hai thành phố.
  • Loại 3: Với hai thành phố \(u\) và \(v\), xét đường đi đơn từ \(u\) đến \(v\). Hãy tìm giá trị lớn nhất có thể đạt được khi chọn một đoạn liên tiếp không rỗng trên đường đi đó.
  • Loại 4: Với hai thành phố \(u\) và \(v\), xét đường đi đơn theo chiều từ \(v\) đến \(u\). Hãy tìm giá trị lớn nhất có thể đạt được khi chọn một đoạn liên tiếp không rỗng trên đường đi đó.

• Giá trị của một đoạn hành quân bằng tổng giá trị chiến lược của các thành phố thuộc đoạn trừ đi tổng chi phí của các tuyến đường nằm giữa những thành phố liên tiếp trong đoạn.

• Đoạn được chọn có thể chỉ gồm một thành phố. Trong trường hợp đó, giá trị đoạn chính là giá trị chiến lược của thành phố ấy.
• Mỗi yêu cầu phải được xử lý dựa trên trạng thái chiến trường sau khi thực hiện tất cả các yêu cầu đứng trước nó.

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(Q\), lần lượt là số thành phố và số yêu cầu cần xử lý.
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\), trong đó \(A_i\) là giá trị chiến lược ban đầu của thành phố \(i\).
• \(N - 1\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u\), \(v\), \(w\), mô tả một tuyến đường nối trực tiếp hai thành phố \(u\) và \(v\) với chi phí hành quân ban đầu là \(w\).

• \(Q\) dòng tiếp theo, mỗi dòng mô tả một yêu cầu thuộc một trong bốn dạng:

  • 1 u x: Cập nhật giá trị chiến lược của thành phố \(u\) thành \(x\).
  • 2 u v x: Cập nhật chi phí hành quân của tuyến đường nối trực tiếp hai thành phố \(u\) và \(v\) thành \(x\).
  • 3 u v: Yêu cầu tìm giá trị lớn nhất của một đoạn hành quân liên tiếp không rỗng trên đường đi từ \(u\) đến \(v\).
  • 4 u v: Yêu cầu tìm giá trị lớn nhất của một đoạn hành quân liên tiếp không rỗng trên đường đi từ \(v\) đến \(u\).

• Các yêu cầu được đưa ra theo thứ tự và phải được xử lý lần lượt. Mỗi thao tác cập nhật sẽ ảnh hưởng đến tất cả các yêu cầu xuất hiện sau nó.

Output

• Với mỗi yêu cầu loại 3 hoặc loại 4, in ra một dòng chứa một số nguyên là giá trị lớn nhất của đoạn hành quân liên tiếp không rỗng được chọn trên đường đi tương ứng.
• Các kết quả phải được in theo đúng thứ tự xuất hiện của các yêu cầu trong Input.
• Nếu giá trị lớn nhất là số âm, vẫn phải in ra giá trị đó; không được chọn đoạn rỗng để nhận giá trị 0.

Example

5 8 
4 -5 7 -2 6 
1 2 3 
2 3 4
2 4 1
4 5 2
3 1 3 
3 3 5 
4 1 5 
1 2 10 
3 1 3 
2 2 4 8 
3 1 5 
4 1 5

7 
7 
6 
14 
11 
11