Sum of Squares Subarray

You are given an array A of n integers and q queries. For each query, you are given two indices l and r (1-indexed), and you need to compute the sum of the squares of the elements from index l to index r in the array.

You can use the following prefix sum formula in LaTeX format to solve the problem:

Let $$P[i] = \sum_{k=1}^{i} A[k]^2, \quad P[0]=0.$$ Then for a query given by indices l and r, the result is:

$$Result = P[r] - P[l-1].$$

Your task is to compute the result for every query efficiently.

inputFormat

The input is given in the following format via standard input (stdin):

 n q
 A[1] A[2] ... A[n]
 l1 r1
 l2 r2
 ...
 lq rq

where:

• n is the number of elements in the array.
• q is the number of queries.
• The second line contains n integers representing the array A.
• Each of the next q lines contains two integers l and r indicating the query range (1-indexed).

outputFormat

For each query, output a single line containing the sum of squares of the subarray from index l to r computed according to the formula provided.

## sample

5 3
1 -2 3 4 -5
1 3
2 5
1 5

14
54
55

</p>