from bisect import bisect_right
k,n = map(int,input().split())
a = list(map(int,input().split()))
def f(x): return x//k*n+bisect_right(a,x%k)
for _ in range(int(input())):
    l,r = map(int,input().split())
    print(f(r)-f(l-1))