PAIRSUM  Sum of Pairwise Products
Given N non negative numbers, the task is to answer M queries.
Each query is as follows:
Given u,v you need to find the pairwise product sum (u and v are zero indexed)
a_{u}a_{u} + a_{u+1}a_{u+1} + a_{u+1}a_{u} + a_{u+2}a_{u+2} + a_{u+2}a_{u+1} + a_{u+2}a_{u} + ... + a_{v}a_{v} + a_{v}a_{v1} + ... + a_{v}a_{u}
Input
N a_{0} a_{1} ... a_{N1} M u_{1} v_{1} u_{2} v_{2} ... u_{M} v_{M}
Output
Print the answer for each query in a separate line.
Example
Input: 5 2 0 1 3 3 3 0 2 1 2 3 4 Output: 7 1 27
Constraints
0 <= u <= v < N
N <= 100000
M <= 100000
0 <= a_{i} <= 1000000
hide comments
nadstratosfer:
20170806 10:52:03
Fast IO + O(1) query answers, still TLE in Python :(


kira28:
20161217 12:24:42
Same code:


baadshah_:
20160703 18:52:08
Use scanf and printf 

hmp:
20160522 10:14:08
to avoid TLE for cin/cout not only use ios_base::sync_with_stdio(false); but also tie cin/cout; Last edit: 20160530 03:57:57 

deradler:
20160520 22:19:45
gud ques, derived a general formula ((sum of nos in a range)^2 + sum of squares of numbers)/2. Last edit: 20160520 23:15:19 

ayush sinha:
20160211 10:09:01
recall 10 class maths 

sarvesh_19:
20160205 22:01:13
use scanf printf ,long long int,.O(n+m) possible with DP :) 

Nikhil Sheoran:
20150306 18:20:24
Even with O(M+N) requires fast i/o.. 

Sudarshan K:
20150107 09:00:34
Problem setter. Please move this to Cube Cluster. Can't submit in C/C++. Says Language available only on Cube Cluster. 

AAKASH TYAGI:
20140710 17:29:30
50th problem on spoj :)

Added by:  Manukranth 
Date:  20110920 
Time limit:  0.151s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 