A WA CPP

#include <bits/stdc++.h>
using namespace std;

#define ll long long int
#define X first
#define Y second

const int N = 1e8 + 1, M = 1e5 + 2;
int spf[N];

void sieve()
{
    vector<int> primes;
    for (int i = 2; i < N; ++i)
    {
        if (spf[i] == 0)
        {
            spf[i] = i;
            primes.push_back(i);
        }
        for (int j = 0; j < primes.size() && primes[j] <= spf[i] && i * primes[j] < N; ++j)
        {
            spf[i * primes[j]] = primes[j];
        }
    }
}

// write a segment tree to set range to 1 or 0 and get sum

int lazy[4 * M], tree[4 * M], a[M];

int is_good(int num)
{
    while (num > 1)
    {
        int p = spf[num];
        int cnt = 0;
        while (num % p == 0)
        {
            num /= p;
            cnt++;
        }
        if (cnt % 2 == 0)
            return 0;
    }
    return 1;
}

void build(int node, int start, int end)
{
    if (start == end)
    {
        tree[node] = is_good(a[start]);
        return;
    }
    int mid = (start + end) / 2;
    build(2 * node, start, mid);
    build(2 * node + 1, mid + 1, end);
    tree[node] = tree[2 * node] + tree[2 * node + 1];
}

void propogate(int node, int start, int end)
{
    if (lazy[node] == -1)
        return;
    if (lazy[node] == 0)
        tree[node] = 0;
    else
        tree[node] = end - start + 1;
    if (start != end)
    {
        lazy[2 * node] = lazy[node];
        lazy[2 * node + 1] = lazy[node];
    }
    lazy[node] = -1;
}

void update(int node, int start, int end, int l, int r, int val)
{
    propogate(node, start, end);
    if (start > r || end < l)
        return;
    if (start >= l && end <= r)
    {
        lazy[node] = val;
        propogate(node, start, end);
        return;
    }
    int mid = (start + end) / 2;
    update(2 * node, start, mid, l, r, val);
    update(2 * node + 1, mid + 1, end, l, r, val);
    tree[node] = tree[2 * node] + tree[2 * node + 1];
}

int query(int node, int start, int end, int l, int r)
{
    propogate(node, start, end);
    if (start > r || end < l)
        return 0;
    if (start >= l && end <= r)
        return tree[node];
    int mid = (start + end) / 2;
    return query(2 * node, start, mid, l, r) + query(2 * node + 1, mid + 1, end, l, r);
}

void solve()
{
    sieve();
    int n, q;
    cin >> n >> q;
    memset(lazy, -1, sizeof(lazy));
    memset(tree, 0, sizeof(tree));
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    build(1, 1, n);
    while (q--)
    {
        int type, l, r, x;
        cin >> type >> l >> r;
        if (type == 2)
        {
            cout << query(1, 1, n, l, r) << '\n';
        }
        else
        {
            cin >> x;
            update(1, 1, n, l, r, is_good(x));
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
#endif
    int tc = 1;
    // cin>>tc;
    for (int i = 1; i <= tc; ++i)
    {
        solve();
    }
}