An được giao nhiệm vụ quản lý một chuỗi gồm \(N\) kho chứa hàng dọc theo tuyến đường huyết mạch, được đánh số từ \(1\) đến \(N\). Ban đầu, tất cả các kho đều trống (số lượng hàng hóa bằng \(0\)). An thực hiện \(Q\) hoạt động nhập kho hoặc kiểm kê hàng hóa:

• 1 l r val: Nhập thêm một lượng hàng hóa là \(val\) vào toàn bộ các kho nằm trong khoảng từ chỉ số \(l\) đến chỉ số \(r\).
• 2 l r: Thống kê tổng số lượng hàng hóa đang được lưu trữ tại tất cả các kho trong khoảng từ chỉ số \(l\) đến chỉ số \(r\).

Hãy giúp An viết chương trình quản lý thông tin kho hàng một cách chính xác nhất.

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên dương \(N\) và \(Q\) (\(1 \le N, Q \le 10^5\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa thông tin của một hoạt động thuộc một trong hai định dạng trên (\(1 \le l \le r \le N\), \(0 \le val \le 10^9\)).

Định dạng đầu ra

• Với mỗi hoạt động thống kê loại 2, in ra tổng lượng hàng hóa tìm được trên một dòng.

Ví dụ

Input:

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

Output:

16
13