from bisect import bisect_left, bisect_right
from collections import defaultdict
import math
import sys


def input():
    return sys.stdin.readline().strip()


def main():
    rr, n = map(int, input().split())
    (*a,) = map(int, input().split())
    a.sort()
    q = int(input())

    def calc(x):
        return x // rr * len(a) + bisect_right(a, x % rr)

    for i in range(q):
        l, r = map(int, input().split())
        print(calc(r) - calc(l - 1))


if __name__ == "__main__":
    main()