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$이 주어진다.

둘째 줄에 정수 $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}$이다. 여기서 $\oplus$는 비트 단위 XOR 연산이다. $i=0$이면 $ans_{0}=0$이고, $i \ge 1$이면 $ans_{i}$는 $i$번째 쿼리의 답이다.

$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)$