30095번 - GCD SUM

문제

길이가 $N$인 수열 $a_{1},ドル $a_{2},ドル $\cdots,ドル $a_{N}$이 주어진다. 다음 쿼리를 수행하는 프로그램을 작성하시오.

• $l$ $r$: $a_{l},ドル $a_{l+1},ドル $\cdots,ドル $a_{r}$에서 모든 연속 부분 수열의 $\gcd$의 합을 출력한다. 즉, $\sum_{i=l}^{r}\sum_{j=i}^{r}\gcd(a_{i}, a_{i+1}, \cdots, a_{j})$을 출력한다.

단, 모든 입력 데이터에서 $a$의 모든 연속 부분 수열의 $\gcd$의 합은 10ドル^{18}$을 넘지 않음이 보장된다.

입력

첫째 줄에 정수 $N$이 주어진다.

둘째 줄에 $N$개의 정수 $a_{1},ドル $a_{2},ドル $\cdots,ドル $a_{N}$이 주어진다.

셋째 줄에 쿼리의 개수를 나타내는 정수 $Q$가 주어진다.

이후 $Q$개의 줄에 쿼리에 대한 정보가 주어진다. 이 중 $i$번째 줄에는 두 정수 $x_{i}$와 $y_{i}$가 주어진다.

$i$번째 쿼리에서 $l$과 $r$의 값을 각각 $l_{i}$와 $r_{i}$라 할 때, $l_{i} = x_{i} \oplus ans_{i-1},ドル $r_{i} = y_{i} \oplus ans_{i-1}$이다. 이때, $i=0$이면 $ans_{0}=0$이고, $i \ge 1$이면 $ans_{i}$를 $i$번째 쿼리에 대한 답으로 정의한다. 여기서 $\oplus$는 bitwise XOR 연산을 나타낸다.

출력

$Q$개의 수를 한 줄에 하나씩 출력한다. $i$번째 줄에는 $i$번째 쿼리에 대한 답을 출력한다.

제한

• 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)$
• $a$의 모든 연속 부분 수열의 $\gcd$의 합은 10ドル^{18}$을 넘지 않는다.
• 1ドル \le l_i \le r_i \le N$ $(1 \le i \le Q)$

노트