디버그

Seán은 자기가 쓴 코드를 디버그하고 있다. 먼저 정수 $N$개짜리 배열 seq를 만들고 전부 0으로 채운다. 그다음 C++로 작성한 아래 함수를 여러 번 호출한다.

void something( int jump ) {
 int i = 0;
 while( i < N ) {
   seq[i] = seq[i] + 1;
   i = i + jump;
 }
}

이 함수는 인덱스가 jump의 배수인 원소를 모두 1씩 늘린다. 인덱스 0은 모든 jump의 배수라서 호출할 때마다 seq[0]이 1씩 늘어난다.

Seán은 함수를 정확히 $K$번 호출하고, 인자로 $X_1, X_2, \dots, X_K$를 이 순서대로 넘긴다.

호출이 모두 끝나면 Seán은 확인하고 싶은 구간 $Q$개를 고른다. 각 구간은 왼쪽 끝 $L$과 오른쪽 끝 $R$ ($L \le R$)로 정해진다. 구간마다 seq[L] + seq[L+1] + ... + seq[R]을 구하라.

첫째 줄에 배열의 크기 $N$과 함수 호출 횟수 $K$가 주어진다 ($1 \le N \le 10^6$, $1 \le K \le 10^6$).

둘째 줄에 함수로 넘기는 인자 $X_1, X_2, \dots, X_K$가 공백으로 구분되어 주어진다 ($1 \le X_i < N$).

셋째 줄에 확인할 구간의 개수 $Q$가 주어진다 ($1 \le Q \le 10^6$).

이어지는 $Q$개 줄에 각 구간의 두 정수 $L_i$와 $R_i$가 주어진다 ($0 \le L_i \le R_i < N$).

$Q$개 줄을 출력한다. $i$번째 줄에는 seq[L_i] + seq[L_i + 1] + ... + seq[R_i]의 값을 출력한다.