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

for i in range(q):
    l, r = map(int, input().split())
    tmp = []
    cnt = 0
    for i in range(l, r + 1):
        tmp.append(i % R)               
    for a in A:
        cnt += tmp.count(a)
    print(cnt)