import bisect

R, N = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
q = int(input())

for i in range(q):
    l, r = map(int, input().split())
    if l // R == r // R:
        cntl = bisect.bisect_left(A, l%R)
        cntr = bisect.bisect_right(A, r%R)
        print(cntr - cntl)
    else:
        ans = ((r // R) - (l // R) - 1) * N
        cntl = bisect.bisect_left(A, l%R)
        cntr = bisect.bisect_right(A, r%R)
        ans += cntr + (N - cntl)
        print(ans)