BÀI 4: MÀN ẢO THUẬT TRÊN BẢNG QUẢNG CÁO

• Vượt qua bao nhiêu thử thách, cuối cùng Pitomon cũng chạy được đến Quảng trường Trung tâm để chờ trực thăng cứu hộ đưa cậu thoát khỏi thế giới máy tính. Tuy nhiên, lực lượng cảnh sát an ninh của hệ thống đã phát giác và đang dùng radar quét "tổng năng lượng cộng hưởng lớn nhất" để dò tìm vị trí chính xác của cậu.

• Bao quanh quảng trường là một dải đèn LED khổng lồ gồm \(N\) bóng đèn, hiển thị các chỉ số năng lượng được biểu diễn bằng một dãy số nguyên \(A_1, A_2, ..., A_N\). Để làm mù radar của cảnh sát, Pitomon đã hack vào hệ thống nguồn điện, liên tục đảo cực các đoạn đèn LED. Cùng lúc đó, cảnh sát không ngừng quét các đoạn đèn để tìm mức năng lượng lớn nhất.

• Trận chiến cuối cùng này là một cuộc rượt đuổi bằng thuật toán kịch tính. Sẽ có \(Q\) thao tác xảy ra, mỗi thao tác thuộc một trong hai loại sau:

• Loại 1 (Pitomon hack): Nhập vào \(1\) \(L\) \(R\). Hệ thống đảo cực nguồn điện của đoạn từ \(L\) đến \(R\). Việc này làm cho tất cả các giá trị năng lượng trong đoạn này bị đổi dấu (biến \(A_i\) thành \(-A_i\) với mọi \(L \le i \le R\)).
• Loại 2 (Cảnh sát quét): Nhập vào \(2\) \(L\) \(R\). Hệ thống radar đo mức năng lượng cộng hưởng lớn nhất của một dải đèn con liên tiếp nằm hoàn toàn trong đoạn \([L, R]\). Cụ thể, tìm giá trị lớn nhất của tổng \(\sum_{k=i}^{j} A_k\) với \(L \le i \le j \le R\). (Lưu ý: Nếu mọi giá trị trong đoạn đều âm, cảnh sát sẽ không thu thập được gì, tương đương với việc chọn một đoạn rỗng có tổng năng lượng bằng \(0\)).

Bạn hãy viết một chương trình mô phỏng lại hệ thống radar để xem cảnh sát có thể đo được mức năng lượng lớn nhất là bao nhiêu sau mỗi lần quét nhé!

Input

• Dòng đầu tiên chứa hai số nguyên dương \(N\) và \(Q\) — số lượng bóng đèn LED và số lượng thao tác.
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, ..., A_N\) (\(|A_i| \le 10^9\)) — chỉ số năng lượng ban đầu của các bóng đèn.
• \(Q\) dòng tiếp theo, mỗi dòng mô tả một thao tác có dạng 1 L R hoặc 2 L R (\(1 \le L \le R \le N\)).

Output

• Đối với mỗi thao tác Loại 2, in ra một số nguyên duy nhất là mức năng lượng cộng hưởng lớn nhất tìm được trên một dòng.

Scoring

• Subtask 1 (30% số điểm): \(N, Q \le 5000\).
• Subtask 2 (30% số điểm): \(N, Q \le 100,000\). Các thao tác loại 1 luôn có \(L = R\).
• Subtask 3 (40% số điểm): \(N, Q \le 100,000\). Không có giới hạn gì thêm.

Sample Input 1

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

Sample Output 1

6
9
3

Sample Input 2

4 4
-3 -1 -4 -2
2 1 4
1 2 2
2 1 4
1 3 3

Sample Output 2

0
1

Giải thích

Ở ví dụ thứ nhất:

- Mảng ban đầu: [5, -2, 3, -4, 1].
- Truy vấn 1 (2 1 5): Đoạn con có tổng lớn nhất là [5, -2, 3] với tổng bằng 6. In ra 6.
- Truy vấn 2 (1 2 4): Đảo cực từ vị trí 2 đến 4. Mảng trở thành: [5, 2, -3, 4, 1].
- Truy vấn 3 (2 1 5): Đoạn con có tổng lớn nhất là toàn bộ mảng [5, 2, -3, 4, 1] với tổng bằng 9. In ra 9.
- Truy vấn 4 (1 1 5): Đảo cực toàn bộ mảng. Mảng trở thành: [-5, -2, 3, -4, -1].
- Truy vấn 5 (2 1 5): Đoạn con có tổng lớn nhất là [3] với tổng bằng 3. In ra 3.