Polynomial Queries

Source: CSES

Version: Phuoc Hung OJ Extended

Problem Statement

Maintain an array. Query 1 a b adds $1,2,\ldots,b-a+1$ to consecutive positions $a,\ldots,b$. Query 2 a b asks for the range sum.

Input

The first line contains $n,q$. The second line contains $t_1,\ldots,t_n$. Each of the next $q$ lines is 1 a b (add $1,2,\ldots,b-a+1$ to consecutive positions) or 2 a b (query the range sum).

Output

For each type-2 query, print the range sum.

Subtasks

• Subtask 1 (20%): size and operation count at most 30; all other validity conditions are unchanged.

• Subtask 2 (30%): size and operation count at most 3000; all other validity conditions are unchanged.

• Subtask 3 (50%): full constraints:

• $1\le n,q\le2\cdot10^5$

• $1\le t_i\le10^6$

• $1\le a\le b\le n$

Examples

Input

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

Output

17
32

Explanation

The initial sum is 17. After 1 1 5, the array becomes [5,4,6,5,12], whose sum is 32.