SP9569 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 $ _{v-1} $ + ... + a $ _{v} $ a $ _{u} $

``` N a0 a1 ... aN-1 M u1 v1 u2 v2 ... uM vM ```

Print the answer for each query in a separate line.