Description

In Madeline’s dream, the border of the city is made up of cosmic fragments of various sizes.

Each cosmic fragment has an energy value. Because the fragments vary in size, their energy values can be large or small.

Madeline enjoys moving between fragments. Each time, she chooses two cosmic fragments and gains a happiness value equal to the greatest common divisor of their energy values. Note that the two fragments can be the same.

The cosmic fragments form a sequence $a_1,a_2,\cdots,a_n$. Each time, Madeline chooses an interval of this sequence, and for any two cosmic fragments $(u,v)$ inside this interval, she will move between them once. Note that $(u,v)$ here is an ordered pair.

Formally, the happiness value Madeline gains each time is

When Madeline is awakened from her dream, she finds that all cosmic fragments have disappeared. She cannot remember the happiness value she got from each move in the dream, and only vaguely remembers the intervals she chose.

So she comes to you, an informatics expert, and asks you to restore the happiness value she obtained at that time based on the intervals she chose each time.

Input Format

The first line contains two positive integers $n,q$, representing the number of fragments and the number of queries.

The second line contains $n$ positive integers $a_1,a_2,\cdots,a_n$, representing the energy value of each fragment.

The next $q$ lines each contain two integers $l_i,r_i$, representing the interval Madeline chose in the $i$-th query.

Output Format

For each query, output one line representing the total sum of happiness values Madeline obtains in that query.

5 2
1 2 3 4 5
1 2
2 3

5
7

Hint

• For $10\%$ of the testdata, $n,q\leq 200$.
• For $20\%$ of the testdata, $n,q\leq 2250$.
• For $40\%$ of the testdata, $n,q\leq 4000$.
• For $100\%$ of the testdata, $n,q,a_i\leq 10^5$.

It is guaranteed that both the sequence and the queries are generated randomly.

Translated by ChatGPT 5