fun main(){
    val data = readln().split(" ").map { it.toInt()}
    val round = data[0]
    val n = data[1]
    val a = readln().split(" ").map { it.toInt()}

    val q = readln().toInt()
    for (j in 0..q-1){
        val data1 = readln().split(" ").map { it.toInt()}
        val ll = data1[0]
        val rr = data1[1]
        var count = 0
        for (t in ll..rr){

            for (i in 0..n-1) {
                if (t % round == a[i]) {
                    count = count + 1
                }


            }


        }
        println(count)
    }
}