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.

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
# 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])


# 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])



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])

# 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])

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])

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])

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
from collections import defaultdict
from math import sqrt

"""def isprime(n):
    if n==2:
        return True
    elif n>2:
        for i in range(2,int(sqrt(n))+1):
            if n%i==0:
                return False
    elif n<2:
        return False
    return True"""

def primefact(n):
    pf = []
    if n%2==0:
        pf.append(2)
        while n%2==0:
            n //= 2
    for i in range(3,int(sqrt(n))+1):
        if n%i==0:
            while n%i==0:
                n //= i
            pf.append(i)
    if n>2:
        pf.append(int(n))
    return pf
    
K,Q = map(int, input().split())
prime_range = {}
pfk = primefact(K)
for i in range(Q):
    query = input().split()
    if query[0]=="!":
        l = int(query[1])
        r = int(query[2])
        start = l
        end = r
        for i in sorted(prime_range):
            if start>i[1]:
                continue
            if end<i[0]:
                break
            startrange = start
            endrange = end
            if start>=i[0] and start<=i[1]:
                start = i[1]+1
                continue
            if end>=i[0]:
                endrange = i[0]-1
            if (startrange<=endrange):
                prime_range[(startrange,endrange)] = int(query[3])
                start = max(endrange+1,i[1]+1)
        if start<=end:
            prime_range[(start,end)] = int(query[3])
    else:
        l = int(query[1])
        r = int(query[2])
        res = []
        count = 0
        for primenum in pfk:
            for currRange in prime_range:
                if (not (r < currRange[0] or l > currRange[1])) :
                    num = prime_range[currRange]
                    if (num % primenum == 0) :
                        count += 1
                        break
        res.append(count)
        for r in res:
            print(r)
        '''for i in prime_range:
            if l>=i[0] and l<=i[1]:
                x = prime_range[(i[0],i[1])]
                pf = primefact(x)
                for p in pf:
                    if p in pfk and p not in pfc:
                        pfc.append(p)
                continue
            if r>=i[0] and r<=i[1]:
                x = prime_range[(i[0],i[1])]
                pf = primefact(x)
                for p in pf:
                    if p in pfk and p not in pfc:
                        pfc.append(p)
        print(len(pfc))
       #print(prime_range)'''
                
            
        

# cook your dish here
import math

def distinctPrimeFactors(num) :
    primes = set()

    if (num == 2) :
        primes.add(num)
    
    sqrt = int(math.sqrt(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 = 0
lst = {}
primes = {}
rangeData = {}
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 = int(l)
        r = int(r)
        x = int(x)
        start = l
        end = r
        startflag = False
        for i in sorted(rangeData) :
            rangeVal = i

            if (start > rangeVal[1]) :
                continue
            if (end < rangeVal[0]) :
                break
            
            startRange = start
            endRange = 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 = int(l)
        r = int(r)
        count = 0
        for primenum in primes[k] :
            for currRange in rangeData :
                if (not (r < currRange[0] or l > currRange[1])) :
                    num = rangeData[currRange]
                    if (num % primenum == 0) :
                        count += 1
                        break
        c += 1
        res.append(count)
    
for i in range(c) :
    print(res[i])

import math

def distinctPrimeFactors(num) :

    primes = set()

    if (num == 2) :
        primes.add(num)
    
    sqrt = int(math.sqrt(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)



lst = {}
primes = {}
rangeData = {}
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 = int(l)
        r = int(r)
        x = int(x)
        start = l
        end = r
        startflag = False
        for i in sorted(rangeData) :
            rangeVal = i
            if (start > rangeVal[1]) :
                continue
            if (end < rangeVal[0]) :
                break
            
            startRange = start
            endRange = 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 = int(l)
        r = int(r)
        count = 0
        for primenum in primes[k] :
            for currRange in rangeData :
                if (not (r < currRange[0] or l > currRange[1])) :
                    num = rangeData[currRange]
                    if (num % primenum == 0) :
                        count += 1
                        break
        print(count)
    
   


import math

def distinctPrimeFactors(num) :

    primes = set()

    if (num == 2) :
        primes.add(num)
    
    sqrt = int(math.sqrt(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)



lst = {}
primes = {}
rangeData = {}
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 = int(l)
        r = int(r)
        x = int(x)
        start = l
        end = r
        startflag = False
        for i in sorted(rangeData) :
            rangeVal = i
            if (start > rangeVal[1]) :
                continue
            if (end < rangeVal[0]) :
                break
            
            startRange = start
            endRange = 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 = int(l)
        r = int(r)
        count = 0
        for primenum in primes[k] :
            for currRange in rangeData :
                if (not (r < currRange[0] or l > currRange[1])) :
                    num = rangeData[currRange]
                    if (num % primenum == 0) :
                        count += 1
                        break
        print(count)
    
   


import math
def distinctPrimeFactors(num) :
    primes = set()
    if (num == 2) :
        primes.add(num)
    sqrt = int(math.sqrt(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)
lst = {}
primes = {}
rangeData = {}
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 = int(l)
        r = int(r)
        x = int(x)
        start = l
        end = r
        startflag = False
        for i in sorted(rangeData) :
            rangeVal = i
            if (start > rangeVal[1]) :
                continue
            if (end < rangeVal[0]) :
                break
            startRange = start
            endRange = 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 = int(l)
        r = int(r)
        count = 0
        for primenum in primes[k] :
            for currRange in rangeData :
                if (not (r < currRange[0] or l > currRange[1])) :
                    num = rangeData[currRange]
                    if (num % primenum == 0) :
                        count += 1
                        break
        print(count)

# Contest Code: DEMA2019     Problem Code: MAXSPSUM
#
# Author: Keyur Shroff
# Date: 26 April 2019

import math

# Function to return the distinct prime factors of an array or a list
def distinctPrimeFactors(num) :

    # use set to store distinct factors
    primes = set()

    if (num == 2) :
        primes.add(num)
    
    sqrt = int(math.sqrt(num))
    for j in range(2, sqrt + 1) :
        if (num % j == 0) :
            # if j is a factor store it in the set
            primes.add(j)
            
            # divide the number with j till it is divisible so that 
            # only prime factors are stored
            while (num % j == 0) :
                num //= j

    # if the number is still greater than 1 then it is a prime factor
    if (num > 2) :
        primes.add(num)

    return (primes)


# --- Main Program ---
lst = {}
primes = {}
rangeData = {}
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 = int(l)
        r = int(r)
        x = int(x)
        start = l
        end = r
        startflag = False
        for i in sorted(rangeData) :
            rangeVal = i
            if (start > rangeVal[1]) :
                continue
            if (end < rangeVal[0]) :
                break
            
            startRange = start
            endRange = 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 = int(l)
        r = int(r)
        count = 0
        for primenum in primes[k] :
            for currRange in rangeData :
                if (not (r < currRange[0] or l > currRange[1])) :
                    num = rangeData[currRange]
                    if (num % primenum == 0) :
                        count += 1
                        break
        print(count)
    
    #print("query=", query, "primes=", primes, "rangeData=", rangeData)