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.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = '# cook your dish here\nfrom collections import defaultdict\nfrom math import sqrt\n\n"""def isprime(n):\n    if n==2:\n        return True\n    elif n>2:\n        for i in range(2,int(sqrt(n))+1):\n            if n%i==0:\n                return False\n    elif n<2:\n        return False\n    return True"""\n\ndef primefact(n):\n    pf = []\n    if n%2==0:\n        pf.append(2)\n        while n%2==0:\n            n //= 2\n    for i in range(3,int(sqrt(n))+1):\n        if n%i==0:\n            while n%i==0:\n                n //= i\n            pf.append(i)\n    if n>2:\n        pf.append(int(n))\n    return pf\n    \nK,Q = map(int, input().split())\nprime_range = {}\npfk = primefact(K)\nfor i in range(Q):\n    query = input().split()\n    if query[0]=="!":\n        l = int(query[1])\n        r = int(query[2])\n        start = l\n        end = r\n        for i in sorted(prime_range):\n            if start>i[1]:\n                continue\n            if end<i[0]:\n                break\n            startrange = start\n            endrange = end\n            if start>=i[0] and start<=i[1]:\n                start = i[1]+1\n                continue\n            if end>=i[0]:\n                endrange = i[0]-1\n            if (startrange<=endrange):\n                prime_range[(startrange,endrange)] = int(query[3])\n                start = max(endrange+1,i[1]+1)\n        if start<=end:\n            prime_range[(start,end)] = int(query[3])\n    else:\n        l = int(query[1])\n        r = int(query[2])\n        res = []\n        count = 0\n        for primenum in pfk:\n            for currRange in prime_range:\n                if (not (r < currRange[0] or l > currRange[1])) :\n                    num = prime_range[currRange]\n                    if (num % primenum == 0) :\n                        count += 1\n                        break\n        res.append(count)\n        for r in res:\n            print(r)\n        \'\'\'for i in prime_range:\n            if l>=i[0] and l<=i[1]:\n                x = prime_range[(i[0],i[1])]\n                pf = primefact(x)\n                for p in pf:\n                    if p in pfk and p not in pfc:\n                        pfc.append(p)\n                continue\n            if r>=i[0] and r<=i[1]:\n                x = prime_range[(i[0],i[1])]\n                pf = primefact(x)\n                for p in pf:\n                    if p in pfk and p not in pfc:\n                        pfc.append(p)\n        print(len(pfc))\n       #print(prime_range)\'\'\'\n                \n            \n        '
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 14383