Lord Voldemort's army has arrived at Hogwarts and the professors are engaging all defences. To optimally use the Protego Maxima spell, they require some information regarding the state of the army.
The army consists of N death eaters that are standing in a line, and each have some initial strength.

To decide how to distribute the power of the protection spell in a particular segment, the professors need to know how many death eaters in that segment have strength in a particular range of values.
Also, the Dark Lord knows about this and hence keeps increasing the strength of some of his death eaters.

Given the initial strength values of all N death eaters as an array A, you must answer T queries of either of the following types:

1 L R P Q
Find the sum of the strengths of death eaters, standing at positions in the range [L,R] ,
that have strength values in the range [P,Q] .

2 L R K
Add K to the strengths of all death eaters standing in the range [L,R] .

Note -
Follow 1-based indexing i.e. the positions are 1.....N
All ranges mentioned are inclusive i.e. [L,R] means L<=i<=R

Input
The first line contains 2 integers N, T - no. of death eaters and no. of queries.
The second line contains N values, for initial strength Ai of each death eater.
Each of the next T lines contains a query in the format 1 L R P Q or 2 L R K

Output
For each query of type 1, print the required sum in a new line

Constraints
1 <= N <= 4000000
1 <= T <= 5000
1 <= L <= R <= N
0 <= P <= Q <= 10^9
0 <= Ai, K <= 10

Use of Fast I/O is recommended.