R,N=list(map(int,input().split()))
A=list(map(int,input().split()))
A=set(A)
Q=int(input())
for i in range(Q):
	l,r=list(map(int,input().split()))
	cnt=0
	for b in range(l,r+1):
		if b%R in A:
			cnt+=1
	print(cnt)