tanya-and-queries

Recently Tanya had breakup with his boyfriend and now she is looking for someone who can understand her and take care of her.
So Tanya formulated a problem and puts a condition that whosoever will first solve the problem, she would make him her boyfriend.
Tanya defines the problem as follows.

Given an array of N elements . You have to perform Q queries on this array. Queries are of the following type

1) 1 i j x --> Add x to array elements from index i to index j.

2) 2 i j x --> Subtract x to array elements from index i to index j.

3) 3 i j x --> Set all array elements from index i to index j to x.

4) 4 i j   --> print the sum of squares of all array elements from index i to index j.

5) 5 i j   --> print the sum of all array elements from index i to index j.

Would you like to be her boyfriend ?

Input:

First line contains N and Q , separated by a single space, denoting the size of array and number of queries respectively.

Next line contains N space integers integers.

Then Q lines follow. There can be 3 or 4 integers,separated by a single space, in each line as described as above.

For queries of type 1,2 and 3 , there will be 4 integers , separated by a single space.

For queries of type 4 and 5 , there will be 3 integers , separated by a single space.

Output:

Print the answer for queries of type 4 and 5 in a new line.

Constraints:

1 ≤ N ≤ 10^5

1 ≤ array element ≤ 100

1 ≤ Q ≤ 10^5

1 ≤ i ≤ j ≤ N

1 ≤ x ≤ 100

SAMPLE INPUT
5 5
1 2 3 4 5
1 1 3 5
2 2 4 3
4 2 5
3 1 5 2
5 1 5

SAMPLE OUTPUT
67
10

Explanation

Inital array      - {1 , 2 , 3 , 4 , 5}
After first query - {6 , 7 , 8 , 4 , 5}
After second query -{6 , 4 , 5 , 1 , 5}

sum of squares = 44 + 55 + 11 + 55 = 67

After third query - {2 , 2 , 2 , 2 , 2}

sum of array = 2 + 2 + 2 + 2 + 2 = 10

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: