The Faith Propagation

Pear lines up \( n \) people, numbered from \(1\) to \(n\). Initially, every person has a faith value of \(0\). Then pear performs \( m \) operations. There are two types of operations:

• Type 1: For given integers \( l \), \( r \) and \( k \), add \( k \) to the faith value of each person from index \( l \) to \( r \) (inclusive). Formally, for every \( i \) such that \( l \le i \le r \), update \( a_i = a_i + k \).
• Type 2: For given integers \( l \) and \( r \), report the sum of the faith values from index \( l \) to \( r \) (inclusive).

You are provided the initial number of people and the list of operations. Your task is to help bx2k compute the correct sums for all query operations.

Note: All formulas must be represented in LaTeX format.

inputFormat

The first line contains two integers \( n \) and \( m \), the number of people and the number of operations respectively.

Each of the following \( m \) lines describes an operation. An operation is given in one of the following formats:

• 1 l r k: For type 1 operation (update), add \( k \) to each person from index \( l \) to \( r \).
• 2 l r: For type 2 operation (query), output the sum of the faith values from index \( l \) to \( r \).

outputFormat

For each type 2 query, output the corresponding sum on a new line.

sample

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

4
18
5