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:

1. Khai thác một cây trong khu rừng. Sau khi khai thác, cây đó bị loại bỏ và các cây còn lại được đánh chỉ số lại (theo thứ tự cũ, liên tiếp từ 1);
2. Chờ đợi thời gian, một số cây liên tục sẽ phát triển cùng một lượng giống nhau;
3. 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í sinh 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.

Dữ liệu

• 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 \le N \le 10^5~, ~1 \le Q \le 10^6~);
• Dòng thứ hai chứa ~N~ số nguyên dương ~a_1, a_2, \dots, a_N~ với ~a_i~ là sản lượng gỗ của cây thứ ~i~ (~1 \le a_i \le 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 (chỉ số cây luôn tính theo thứ tự hiện tại, sau khi đã loại bỏ các cây bị khai thác):
  • 1 p: Khai thác cây thứ ~p~ (Điều 1) (~1 \le p \le 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 \le l, r \le N~; ~1 \le x \le 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 \le l, r \le N~; ~l \le r~).

Kết quả

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 (mỗi yêu cầu Điều 3 một dòng, theo thứ tự xuất hiện).

Ví dụ

TREE.INP

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

TREE.OUT

15
13
22

Giới hạn

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