Hiện nay, chặt phá rừng đang là vấn nạn nhức nhối cho nhân loại. Tại khu rừng F, con người đã chặt phá và khai thác hết 70,96% cây cối trong rừng, dẫn đến sự tuyệt chủng của vô số loài động thực vật quý hiếm. Để đẩy lùi mối nguy hại đó, hiệp hội PU đã lên kế hoạch ngăn chặn, khôi phục lại khu rừng, đưa khu rừng trở lại đúng như hiện trạng ban đầu. Sau hàng chục năm thực hiện, khu rừng đang dần hồi sinh, động thực vật ngày càng phong phú. Một trong những phương pháp mang lại lợi ích nhiều nhất là quy hoạch khai thác.

Hiện tại, trong rừng có \(N\) cây \(X\) đang trong giai đoạn có thể khai thác. Mỗi cây đều cho một sản lượng gỗ cụ thể sau khi khai thác. Tại thời điểm này, hiệp hội PU chỉ cho phép các công ty khai thác làm được 3 Điều sau:

• Khai thác một cây trong khu rừng. Sau khi khai thác, cây đó bị loại bỏ và được đánh chỉ số lại;
• Chờ đợi thời gian, một số cây sẽ liên tục phát triển cùng một lượng giống nhau;
• Thống kê xem tổng sản lượng gỗ của một số cây liên tục nhau.

Được biết, chỉ có hiệp hội PU mới làm được các việc đó, nên số lượng yêu cầu gửi đến hiệp hội ngày càng tăng. Do có quá nhiều yêu cầu nên hiệp hội đã thuê một số người làm công việc này thông qua một bài kiểm tra. Cho \(Q\) yêu cầu giả định, thí sinh phải thực hiện các yêu cầu một cách liên tục và đưa ra các kết quả thống kê. Nếu tất cả các kết quả thống kê chính xác so với đáp án của hiệp hội thì thí sinh được nhận vào làm với một mức lương rất cao.

Yêu cầu: Các thí sính hãy thử sức với bài kiểm tra của hiệp hội PU để được nhận vào làm việc.

Input: Đọc từ file văn bản TREE.INP gồm:

• Dòng đầu tiên chứa hai số nguyên dương \(N\) và \(Q\) lần lượt là số cây đang trong giai đoạn có thể khai thác và số lượng yêu cầu giả định trong bài kiểm tra (\(1 ≤ N ≤ 10^5\), \(1 ≤ Q ≤ 10^6\)).
• Dòng thứ hai chứa \(N\) số nguyên dương \(a_1, a_2, ..., a_N\) với \(a_i\) là sản lượng gỗ của cây thứ \(i\ (1 ≤ a_i ≤ 10^6)\).
• \(Q\) dòng tiếp theo lần lượt là các yêu cầu giả định trong bài kiểm tra theo định dạng như sau:
  • \(1\ p\): Khai thác cây thứ \(p\) (Điều 1) (\(1 ≤ p ≤ N\));
  • \(2\ l\ r\ x\): Các cây từ \(l\) đến \(r\) phát triển thêm \(x\) sản lượng gỗ (Điều 2) (\(1 ≤ l, r ≤ N, 1 ≤ x ≤10^6\));
  • \(3\ l\ r\): Thống kê tổng sản lượng gỗ các cây từ \(l\) đến \(r\) (Điều 3) (\(1 ≤ l, r ≤ N, l ≤ r\)).

Output: Ghi ra file văn bản TREE.OUT gồm một số dòng là tổng sản lượng gỗ khi thực hiện yêu cầu thuộc Điều 3.

Scoring

• Có 50% test tương ứng 50% số điểm của bài với \(1 ≤ N ≤ 100\) và không có yêu cầu thuộc Điều 1;
• Có 30% test tương ứng 30% số điểm của bài với \(1 ≤ N ≤ 10^5\) và không có yêu cầu thuộc Điều 1;
• Có 20% test tương ứng 20% số điểm của bài với \(1 ≤ N ≤ 10^5\), bao gồm cả 3 Điều.

Example

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

15
13
22