Range Sum of Divisor Sums

You are given an array of n positive integers. For each integer, define its divisor sum as the sum of all of its positive divisors. Formally, for an integer \(n\), its divisor sum is given by

\(\sigma(n)=\sum_{d|n} d\)

After preprocessing the array by replacing each element with its divisor sum, you will be given q queries. Each query is defined by two integers \(l\) and \(r\) (1-indexed) and asks for the sum of the processed array elements in the range \([l, r]\).

Your task is to answer all the queries efficiently.

inputFormat

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

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

The following q lines each contain two integers l and r (1-indexed), representing a query asking for the sum of the processed array elements from index l to r (inclusive).

outputFormat

For each query, output a single integer on a new line indicating the sum of divisor sums in the range \([l, r]\).

## sample

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

8
14
21

</p>