GCD SUM

A sequence of length $N$, $a_{1}, a_{2}, \cdots, a_{N}$, is given. Write a program that handles the following query.

• $l$ $r$: Print the sum of the gcd of every contiguous subsequence of $a_{l}, a_{l+1}, \cdots, a_{r}$. In other words, print $\sum_{i=l}^{r}\sum_{j=i}^{r}\gcd(a_{i}, a_{i+1}, \cdots, a_{j})$.

The sum of the gcd over all contiguous subsequences of $a$ is guaranteed not to exceed $10^{18}$ for every input.

The first line contains an integer $N$.

The second line contains $N$ integers $a_{1}, a_{2}, \cdots, a_{N}$.

The third line contains an integer $Q$, the number of queries.

Each of the next $Q$ lines contains two integers $x_{i}$ and $y_{i}$. For the $i$-th query, let $l_{i}$ and $r_{i}$ be the values of $l$ and $r$. Then $l_{i} = x_{i} \oplus ans_{i-1}$ and $r_{i} = y_{i} \oplus ans_{i-1}$, where $\oplus$ is the bitwise XOR operation. If $i=0$, then $ans_{0}=0$. If $i \ge 1$, $ans_{i}$ is the answer to the $i$-th query.

Print $Q$ numbers, one per line. The $i$-th line contains the answer to the $i$-th query.

• $1 \le N \le 500\,000$
• $1 \le a_{i} \le 10^{9}$ $(1 \le i \le N)$
• $1 \le Q \le 100\,000$
• $0 \le x_{i}, y_{i} < 2^{60}$ $(1 \le i \le Q)$
• The sum of the gcd over all contiguous subsequences of $a$ does not exceed $10^{18}$.
• $1 \le l_i \le r_i \le N$ $(1 \le i \le Q)$