프로그램

창영이가 프로그램의 오류를 찾기 위해 디버깅을 하고 있다. 이 프로그램은 크기가 N이고 모든 원소가 0으로 채워진 배열 a를 만든 뒤, 아래의 something 함수를 호출한다.

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

창영이는 이 함수를 K번 호출한다. 매 호출 시 인자로 넘기는 jump 값은 차례대로 X1, X2, X3, …, XK이다.

즉 something(X)를 호출하면 인덱스 0, X, 2X, 3X, … 처럼 X의 배수이면서 N보다 작은 모든 인덱스의 값이 1씩 증가한다.

모든 호출을 마친 뒤 창영이는 배열에 값이 제대로 들어갔는지 확인한다. 확인은 총 Q번 하며, 매번 두 정수 L과 R (L ≤ R)을 정하고 그 구간의 합, 즉 a[L] + a[L+1] + … + a[R] 을 구한다.

함수 호출에 사용한 X 값들과 확인 정보가 주어질 때, 각 확인의 결과(구간 합)를 구하는 프로그램을 작성하시오.

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

둘째 줄에 함수 호출에 사용하는 인자 X1, X2, …, XK가 공백으로 구분되어 주어진다. (1 ≤ Xi < N)

셋째 줄에 확인 횟수 Q가 주어진다. (1 ≤ Q ≤ 10^6)

넷째 줄부터 Q개의 줄에 각 확인에 사용하는 두 정수 L과 R이 주어진다. (0 ≤ L ≤ R < N)

총 Q개의 줄을 출력한다. 각 줄에는 해당 확인의 L과 R에 대해 a[L] + a[L+1] + … + a[R] 의 값을 출력한다.