Given an empty array A of infinite length and a positive integer K you have to process 
Q queries of type:    
- ! l r x: Fill the value x in all the empty places in the array from index l to r  (both inclusive).
- ? l r: Print the number of prime factors of K which is also a prime factor of at least one number in A[l], A[l + 1], A[l + 2], … A[r].   
-----Input-----
- The first line contains two space separated integers K and Q respectively.
- Then Q lines follow:
- Each of the $i^{th}$ line contains one of the above two types of queries.
-----Output-----
For each query of the second type, print in a new line the answer to that query. i.e. number of prime factors of K which is also a prime factor of at least one number in A[l], A[l + 1], A[l + 2], … A[r].   
-----Constraints-----
- $1 \leq K, x \leq 10^9$
- $ 1 \leq l \leq r \leq 10^5$
- $ 1 \leq Q \leq 10^5$ 
-----Sample Input-----
20 5
? 1 5
! 3 5 4
? 1 5
! 1 4 15
? 1 5   
-----Sample Output-----
0
1
2   
-----EXPLANATION-----
Initially, all the places in the array are empty. i.e _ _ _ _ _
After first update the array looks like: _ _ 4 4 4
In the range [1, 5] the only factor of 20 which is also a prime factor of at least one number in _ _ 4 4 4  is 2.
After the second update the array looks like: 15 15 4 4 4
In the range [1, 5] the prime factors of 20 i.e. 5 is a prime factor of 15, 15 and 2 is the prime factor of 4, 4, 4.
# cook your dish here
import math
def distinctPrimeFactors(num) :
    primes,sqrt = set(),int(math.sqrt(num))
    if (num == 2) :primes.add(num)
    for j in range(2, sqrt + 1) :
        if (num % j == 0) :
            primes.add(j)
            while (num % j == 0) :num //= j
    if (num > 2) :primes.add(num)
    return (primes)
res,c,lst,primes,rangeData = [],0,{},{},{};k, q = map(int, input().split());primes[k] = distinctPrimeFactors(k)
for tc in range(q) :
    query = input()
    if (query[0] == '!') :
        cmd, l, r, x = query.split();l,r,x = int(l),int(r),int(x);start,end,startflag = l,r,False
        for i in sorted(rangeData) :
            rangeVal = i
            if (start > rangeVal[1]) :continue
            if (end < rangeVal[0]) :break            
            startRange,endRange = start,end
            if (start >= rangeVal[0] and start <= rangeVal[1]) :start = rangeVal[1] + 1;continue
            if (end >= rangeVal[0]) :endRange = rangeVal[0] - 1
            if (startRange <= endRange) :
                rangeData[(startRange, endRange)] = x;start = max(endRange + 1, rangeVal[1] + 1)
        if (start <= end) :rangeData[(start,end)] = x
    elif (query[0] == '?') :
        cmd, l, r = query.split();l,r,count = int(l),int(r),0
        for primenum in primes[k] :
            for currRange in rangeData :
                if (not (r < currRange[0] or l > currRange[1])) :
                    if (rangeData[currRange] % primenum == 0) :count += 1;break
        c += 1;res.append(count)    
for i in range(c):print(res[i])
# cook your dish here
import math
def distinctPrimeFactors(num) :
    primes,sqrt = set(),int(math.sqrt(num))
    if (num == 2) :primes.add(num)
    for j in range(2, sqrt + 1) :
        if (num % j == 0) :
            primes.add(j)
            while (num % j == 0) :num //= j
    if (num > 2) :primes.add(num)
    return (primes)
res,c,lst,primes,rangeData = [],0,{},{},{};k, q = map(int, input().split());primes[k] = distinctPrimeFactors(k)
for tc in range(q) :
    query = input()
    if (query[0] == '!') :
        cmd, l, r, x = query.split();l,r,x = int(l),int(r),int(x);start,end,startflag = l,r,False
        for i in sorted(rangeData) :
            rangeVal = i
            if (start > rangeVal[1]) :continue
            if (end < rangeVal[0]) :break            
            startRange,endRange = start,end
            if (start >= rangeVal[0] and start <= rangeVal[1]) :start = rangeVal[1] + 1;continue
            if (end >= rangeVal[0]) :endRange = rangeVal[0] - 1
            if (startRange <= endRange) :
                rangeData[(startRange, endRange)] = x;start = max(endRange + 1, rangeVal[1] + 1)
        if (start <= end) :rangeData[(start,end)] = x
    elif (query[0] == '?') :
        cmd, l, r = query.split();l,r,count = int(l),int(r),0
        for primenum in primes[k] :
            for currRange in rangeData :
                if (not (r < currRange[0] or l > currRange[1])) :
                    if (rangeData[currRange] % primenum == 0) :count += 1;break
        c += 1;res.append(count)    
for i in range(c):print(res[i])