Prefix Sum of Squares

You are given an array of n integers. Your task is to answer q queries on the array. Each query provides two integers, l and r, and you need to compute the sum of squares of the array elements from index l to r (both inclusive). It is guaranteed that the indices in the queries are 1-indexed.

To achieve an optimal solution, you are advised to precompute a prefix sum of squares array. Given the array a, the prefix sum of squares array P is defined as:

$$P[i] = \sum_{k=1}^{i} a_k^2$$

Then, the answer for a query (l, r) can be computed in O(1) time using the formula:

$$S(l, r) = P[r] - P[l-1]$$

Implement a program that reads from standard input, processes the queries efficiently, and writes the output to standard output.

inputFormat

The first line contains a single integer n representing the number of elements in the array.

The second line contains n space-separated integers representing the array elements.

The third line contains a single integer q representing the number of queries.

Each of the next q lines contains two space-separated integers l and r representing a query.

outputFormat

For each query, output the sum of squares of the elements in the subarray from index l to r (inclusive) on a new line.

## sample

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

14
29
55

</p>