Trong kỳ thi Học sinh giỏi Duyên Hải – Hải Dương 2024, bạn được yêu cầu giải quyết một bài toán liên quan đến việc quản lý một dãy số. Bạn cần xây dựng một hệ thống có khả năng xử lý hiệu quả các truy vấn cập nhật và truy vấn tổng trên một dãy số. Hệ thống cần hỗ trợ các thao tác sau:

Khởi tạo một dãy số có ~n~ phần tử, xử lý ~q~ truy vấn, mỗi truy vấn là:

• Cộng một giá trị cố định vào tất cả các phần tử trong một đoạn.
• Tính tổng của các phần tử trong một đoạn chỉ định của dãy.

Yêu cầu: Hãy viết chương trình thực hiện các thao tác trên.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~ (~1 \le n, q \le 100000~), lần lượt là số lượng phần tử của dãy và số lượng truy vấn.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (~|a_i| \le 100000~), các phần tử ban đầu của dãy.
• ~q~ dòng tiếp theo, mỗi dòng mô tả một truy vấn:
  • Tác vụ 1: ~u~ ~l~ ~r~ ~val~: Cập nhật giá trị ~val~ cho các phần tử trong đoạn từ ~l~ đến ~r~ (~1 \le l \le r \le n~).
  • Tác vụ 2: ~v~ ~l~ ~r~: Tính tổng các phần tử trong đoạn từ ~l~ đến ~r~ (~1 \le l \le r \le n~).

Output

• Đối với mỗi truy vấn tính tổng đoạn từ ~l, r~, in ra tổng các phần tử trong đoạn từ ~l~ đến ~r~ trên một dòng riêng biệt.

Sample Input 1

5 4
1 2 3 4 5
u 1 3 10
v 1 5
u 2 4 -2
v 2 4

Sample Output 1

45
13