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

```

Measured memory_bytes: 14155