Taco Prime Sum Queries

You are given an integer array of length n and q queries. For each query, you are given two integers l and r (1-indexed) which represent the subarray A[l...r]. Your task is to compute the power value of the subarray – defined as the sum of all prime numbers in that subarray.

More formally, define an indicator function for each element:

[ I(a) = \begin{cases} a, & \text{if } a \text{ is prime} \ 0, & \text{otherwise} \end{cases} ]

Then, for each query, if we precompute a prefix sum array where

[ prefix[i] = \sum_{j=1}^{i} I(A_j), ]

the answer for the query (l, r) is:

[ prefix[r] - prefix[l-1]. ]

Note: The array indices are 1-indexed, and 1 is not considered a prime number.

inputFormat

The first line of input contains two integers n and q separated by a space, where n is the number of elements in the array and q is the number of queries.

The second line contains n integers separated by spaces representing the elements of the array.

Each of the following q lines contains two integers l and r separated by a space, representing a query for the subarray from index l to r.

outputFormat

For each query, output a single integer representing the sum of all prime numbers within the subarray A[l...r]. The answers for each query should be printed on a new line.

## sample

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

10
5
3

</p>