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