Bạn được cho một mảng gồm \(n\) phần tử, mỗi phần tử ban đầu đều bằng \(0\). Bạn sẽ phải thực hiện \(m\) thao tác thuộc \(2\) loại sau:

• Loại 1: 0 l r k - nâng các phần tử từ vị trí \(l\) đến \(r\) lên \(k\) đơn vị.
• Loại 2: 1 l r - in ra tổng các phần tử trong đoạn từ \(l\) đến \(r\).

Input

• Dòng đầu gồm hai số \(n\) và \(m\), lần lượt là số phần tử của mảng và số thao tác cần thực hiện (\(1 \le n \le 10^5, 1 \le m \le 10^5\)).
• \(m\) dòng sau, mỗi dòng thể hiện một thao tác như trên. Dữ liệu đảm bảo (\(1 \le l \le r \le n, 1 \le k \le 10^7\)).

Output

• Với mỗi truy vấn loại 2, in ra câu trả lời tương ứng trên một dòng.

Example

6 4
0 1 3 2
1 1 2
0 2 6 4
1 1 3

4
14