Sum of Squares Queries

Given an array of n integers, your task is to answer several 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\) inclusive.

Formally, given an array \(a\), for each query \((l, r)\) compute:

$$S = \sum_{i=l}^{r} a_i^2$$

You are required to use an efficient method (such as prefix sums) so that even large arrays and many queries can be handled efficiently.

inputFormat

The input is read from stdin and has the following format:

• The first line contains a single integer \(n\) (1 ≤ \(n\) ≤ 10⁵), the number of elements in the array.
• The second line contains \(n\) space-separated integers, representing the elements of the array.
• The third line contains a single integer \(q\), the number of queries.
• Each of the next \(q\) lines contains two space-separated integers \(l\) and \(r\) (1 ≤ \(l\) ≤ \(r\) ≤ \(n\)), representing a query.

outputFormat

For each query, output the sum of squares of the array elements in the specified range. Each result should be printed on a new line to stdout.

## sample

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

14
29
55

</p>