Daddy and Chocolates

All submissions for this problem are available.
Po  the Panda, is the chosen dragon warrior who is destined to bring peace in the universe. He fights evil Kung Fu Masters. He is amazingly witty, but wittier is his master, Master Shifu, who taught him the strongest move he knows, THE WUXI FINGER HOLD. But little does his master know that his skills are not the secret to his power, but chocolates, which his daddy makes for him.
But now, there is trouble in the paradise. Tai Lung has come to defeat the dragon warrior, and to prepare Po, his daddy needs chocolates. But unfortunately, the stock of ingredients to make the chocolates has finished. So daddy rushes to the market to buy the ingredients.
In the market, there is only one shop, and taking benefit of this thing, the shopkeeper charges hefty!
There are a total N ingredients in the shop, each with a cost C_{i}. There is an infinite supply of each ingredient in the shop. The battle will last D days, so each day, daddy buys a contiguous subset of the ingredients defined by index L and R(1 ≤ L ≤ R ≤ N). Daddy buys all ingredients, one each, from index L to R(inclusive).
Now the problem is the calculation of the total cost of the ingredients. The shopkeeper's formula for deciding the total cost of the ingredients is as follows:
Let there be K different ingredients with cost C, so the cost with the normal calculation for all these ingredients should be K*C, but according to the shopkeeper, the cost of these ingredients is K*K*C.
You need to find out the total cost for each day.
Input
First line of the input will contain two integers N and D, the number of ingredients and the number of days respectively.
The second line will have N integers, C_{i} (1 ≤ i ≤ N), denoting the cost of element i.
The next D lines contain two integers L and R, denoting the contiguous array of ingredients daddy needs to buy on this day.
Output
For each day, output a single line containing the total cost of the ingredients for that day.
Constraints
 1 ≤ N,D ≤ 200000
 1 ≤ C_{i} ≤ 1000000
 1 ≤ L ≤ R ≤ N
Example
Input: 3 2 1 2 1 1 2 1 3 Output: 3 6
Input: 8 3 1 1 2 2 1 3 1 1 2 7 1 6 2 7 Output: 20 20 20
Explanation
Example case 1.
The ingredients selected in range [1,3], i.e. day 2.
Total cost = 2*2*1 + 1*1*2 = 6
Example case 2.
Consider the following array, and the ingredients selected in range [2,7], i.e. day 1.
Total cost = 3*3*1 + 2*2*2 + 1*1*3 = 20
Author:  sahilarora.535 
Editorial  https://discuss.codechef.com/problems/DDCC 
Tags  dmnt2016, medium, moalgorithm, sahilarora.535 
Date Added:  29032016 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions