Trong một cửa hàng đồ chơi, có \(n\) món đồ chơi được xếp thành một hàng. Các món đồ chơi được đánh số đánh số từ \(1\) đến \(n\) (từ trái sang phải). Ban đầu, món đồ chơi thứ \(i\) có giá là \(a_{i}\) đồng.

Nhân ngày 26 tháng 10 năm 2024, bạn Trung mua đồ chơi tặng hai em An và Bình. Do không biết các em của mình thích đồ chơi như thế nào, bạn Trung quyết định mua một số món đồ chơi liên tiếp trên hàng, chia chúng thành hai tập (mỗi tập gồm các món đồ chơi có chỉ số liên tiếp nhau và mỗi món đồ chơi thuộc đúng một đoạn). Sau đó tặng cho hai em của mình mỗi người một tập.

Do bạn Trung là một người rất có tâm nên Trung muốn tìm cách chia sao cho chênh lệch giá trị các món qùa mà An và Bình được nhận là nhỏ nhất.

Tuy nhiên, hôm nay là một ngày rất đặc biệt nên có rất nhiều sự kiện xảy ra liên tục, ta có thể chia chúng thành hai loại:

• \(1\) \(i\) \(x\): Chủ quán gỡ món đồ chơi thứ \(i\) xuống và thay vào đó một món đồ chơi khác có giá là \(x\).
• \(2\) \(l\) \(r\): Bạn Trung tự hỏi rằng, nếu mua các món đồ liên tiếp từ \(l\) đến \(r\), chênh lệch giá trị các món đồ được nhận của hai em là bao nhiêu.

Với mỗi sự kiện loại hai, hãy giúp bạn Trung bằng cách trả lời câu hỏi của Trung.

Input

• Dòng đầu tiên gồm \(2\) số nguyên dương \(n\) và \(q\) \((1 \leq n, q \leq 2 \times 10^{6})\) - Số lượng món đồ chơi trong cửa hàng và số sự kiện xảy ra hôm nay.
• Dòng thứ hai gồm \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_{n}\) \((1 \leq a_{i} \leq 10^{9})\) - Giá trị của các món đồ chơi.
• Dòng thứ \(i\) trong \(q\) dòng tiếp theo mô tả về sự kiện thứ \(i\) thuộc một trong hai loại sau:
  • \(1\) \(i\) \(x\) \((1 \leq i \leq n, 1 \leq x \leq 10^{9})\) mô tả sự kiện loại \(1\).
  • \(2\) \(l\) \(r\) \((1 \leq l \leq r \leq n)\) mô tả sự kiện loại \(2\).

Output

• Gồm một số dòng, dòng thứ \(i\) là câu trả lời cho sự kiến loại hai thứ \(i\).

Scoring

• Subtask \(1\) (\(22\%\) số điểm): \(n, q \leq 5000\).
• Subtask \(2\) (\(24\%\) số điểm): Không có sự kiện loại một.
• Subtask \(3\) (\(26\%\) số điểm): \(n, q \leq 2 \times 10^{5}\).
• Subtask \(4\) (\(28\%\) số điểm): không có rằng buộc gì thêm.

Example

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

1
2

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

0
1
3
2
1