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 = "import math\r\n\r\ndef distinctPrimeFactors(num) :\r\n\r\n    primes = set()\r\n\r\n    if (num == 2) :\r\n        primes.add(num)\r\n    \r\n    sqrt = int(math.sqrt(num))\r\n    for j in range(2, sqrt + 1) :\r\n        if (num % j == 0) :\r\n            \r\n            primes.add(j)\r\n            \r\n           \r\n            while (num % j == 0) :\r\n                num //= j\r\n\r\n   \r\n    if (num > 2) :\r\n        primes.add(num)\r\n\r\n    return (primes)\r\n\r\n\r\n\r\nlst = {}\r\nprimes = {}\r\nrangeData = {}\r\nk, q = map(int, input().split())\r\nprimes[k] = distinctPrimeFactors(k)\r\nfor tc in range(q) :\r\n    query = input()\r\n    if (query[0] == '!') :\r\n        cmd, l, r, x = query.split()\r\n        l = int(l)\r\n        r = int(r)\r\n        x = int(x)\r\n        start = l\r\n        end = r\r\n        startflag = False\r\n        for i in sorted(rangeData) :\r\n            rangeVal = i\r\n            if (start > rangeVal[1]) :\r\n                continue\r\n            if (end < rangeVal[0]) :\r\n                break\r\n            \r\n            startRange = start\r\n            endRange = end\r\n            if (start >= rangeVal[0] and start <= rangeVal[1]) :\r\n                start = rangeVal[1] + 1\r\n                continue\r\n            if (end >= rangeVal[0]) :\r\n                endRange = rangeVal[0] - 1\r\n            if (startRange <= endRange) :\r\n                rangeData[(startRange, endRange)] = x\r\n                start = max(endRange + 1, rangeVal[1] + 1)\r\n        if (start <= end) :\r\n            rangeData[(start,end)] = x\r\n    elif (query[0] == '?') :\r\n        cmd, l, r = query.split()\r\n        l = int(l)\r\n        r = int(r)\r\n        count = 0\r\n        for primenum in primes[k] :\r\n            for currRange in rangeData :\r\n                if (not (r < currRange[0] or l > currRange[1])) :\r\n                    num = rangeData[currRange]\r\n                    if (num % primenum == 0) :\r\n                        count += 1\r\n                        break\r\n        print(count)\r\n    \r\n   \r\n"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13999