fun main() {
        val (round, n) = readln().split(" ").map { it.toInt() }
        val a = readln().split(" ").map { it.toInt() }
            .sorted().toMutableList()
        val q = readln().toInt()

        for(i in 0..<n) {
            a.add(a[i] + round)
        }

        for(i in 0..<q) {
            var (l, r) = readln().split(" ").map { it.toInt() }
            var cnt = (r - l) / round * n

            // 0 <= l < R
            // l < r < 2R
            l %= round
            r %= round
            if(r < l) r += round

            var li = a.binarySearch(l)
            val lExist = li >= 0
            if(li < 0) li += 2*n

            var ri = a.binarySearch(r)
            val rExist = ri >= 0
            if(ri < 0) ri += 2*n

            if(lExist != rExist) {
                cnt += 1
            }

            cnt += ri - li
            println(cnt)
        }
    }