Problem Statement

You are given a sequence $A = \{ a_1, a_2, ... , a_N \} \ $ with $N$ elements.

A total of $Q$ queries of the following 1 type are given, so process them in order.

• $1 \ l \ r \ x$

  • Output the value of $\displaystyle \sum_{i \in [l, r]} \max(a_i - x, 0) $

Input

$N \ Q$
$a_1 \ a_2 \ \cdots \ a_N$
$query_1$
$query_2$
$\cdots$
$query_Q$

The first line contains an integer $N$ representing the length of the sequence and an integer $Q$ representing the number of queries, in this order, separated by a single-byte space.

The second line contains $N$ integers separated by single-byte spaces, where the $i$-th integer $(1 \le i \le N)$ represents the initial value of $a_i$.

The $i$-th $(1 \le i \le Q)$ of the following $Q$ lines contains the $i$-th query.

Each query is given in one of the following formats:

• $1 \ l \ r \ x$

The formats are as listed above.

The input consists of $Q + 2$ lines in total and satisfies the following constraints.

• All input values are integers
• $1 \le N, Q \le 10^5$
• $1 \le a_i \le 10^9 \ \ (1 \le i \le N)$
• Query 1
  • $1 \le l \le r \le N$
  • $1 \le x \le 10^9$

Output

For each query 1, output the value of $\displaystyle \sum_{i \in [l, r]} \max(a_i - x, 0) $, separated by newlines.

Sample

5 4
13 3 3 133 1333
1 1 5 1
1 1 5 100
1 2 3 3
1 4 5 33

1480
1266
0
1400