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

typedef long long ll;

const int MAXN = 100005;
const ll INF = -1; // no lazy assign pending

struct Node {
    ll sum, mn, mx;
    ll lazy; // -1 = no pending assign
};

int n, q;
Node tree[4 * MAXN];

void build(int node, int l, int r, ll* A) {
    tree[node].lazy = INF;
    if (l + 1 == r) {
        tree[node].sum = tree[node].mn = tree[node].mx = A[l];
        return;
    }
    int mid = (l + r) / 2;
    build(2*node, l, mid, A);
    build(2*node+1, mid, r, A);
    tree[node].sum = tree[2*node].sum + tree[2*node+1].sum;
    tree[node].mn = min(tree[2*node].mn, tree[2*node+1].mn);
    tree[node].mx = max(tree[2*node].mx, tree[2*node+1].mx);
}

void pushdown_assign(int node, int l, int r, ll val) {
    int len = r - l;
    tree[node].sum = val * len;
    tree[node].mn = tree[node].mx = val;
    tree[node].lazy = val;
}

void pushdown(int node, int l, int r) {
    if (tree[node].lazy != INF) {
        int mid = (l + r) / 2;
        pushdown_assign(2*node, l, mid, tree[node].lazy);
        pushdown_assign(2*node+1, mid, r, tree[node].lazy);
        tree[node].lazy = INF;
    }
}

void pull(int node) {
    tree[node].sum = tree[2*node].sum + tree[2*node+1].sum;
    tree[node].mn = min(tree[2*node].mn, tree[2*node+1].mn);
    tree[node].mx = max(tree[2*node].mx, tree[2*node+1].mx);
}

// Query 0: range sum
ll query_sum(int node, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return tree[node].sum;
    pushdown(node, l, r);
    int mid = (l + r) / 2;
    ll res = 0;
    if (ql < mid) res += query_sum(2*node, l, mid, ql, qr);
    if (qr > mid) res += query_sum(2*node+1, mid, r, ql, qr);
    return res;
}

// Query 1: range assign
void update_assign(int node, int l, int r, int ql, int qr, ll val) {
    if (ql <= l && r <= qr) {
        pushdown_assign(node, l, r, val);
        return;
    }
    pushdown(node, l, r);
    int mid = (l + r) / 2;
    if (ql < mid) update_assign(2*node, l, mid, ql, qr, val);
    if (qr > mid) update_assign(2*node+1, mid, r, ql, qr, val);
    pull(node);
}

// Query 2: range isqrt
void update_isqrt(int node, int l, int r, int ql, int qr) {
    if (ql >= r || l >= qr) return;
    // If min and max have same isqrt, treat as range assign
    ll sq_mn = (ll)sqrtl(tree[node].mn);
    while (sq_mn * sq_mn > tree[node].mn) sq_mn--;
    while ((sq_mn+1)*(sq_mn+1) <= tree[node].mn) sq_mn++;
    ll sq_mx = (ll)sqrtl(tree[node].mx);
    while (sq_mx * sq_mx > tree[node].mx) sq_mx--;
    while ((sq_mx+1)*(sq_mx+1) <= tree[node].mx) sq_mx++;
    
    if (ql <= l && r <= qr && sq_mn == sq_mx) {
        pushdown_assign(node, l, r, sq_mn);
        return;
    }
    if (l + 1 == r) {
        // leaf
        tree[node].sum = tree[node].mn = tree[node].mx = sq_mn;
        tree[node].lazy = INF;
        return;
    }
    pushdown(node, l, r);
    int mid = (l + r) / 2;
    update_isqrt(2*node, l, mid, ql, qr);
    update_isqrt(2*node+1, mid, r, ql, qr);
    pull(node);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> q;
    ll A[n];
    for (int i = 0; i < n; i++) cin >> A[i];
    
    build(1, 0, n, A);
    
    while (q--) {
        int type;
        cin >> type;
        if (type == 0) {
            int l, r;
            cin >> l >> r;
            cout << query_sum(1, 0, n, l, r) << '\n';
        } else if (type == 1) {
            int l, r; ll x;
            cin >> l >> r >> x;
            update_assign(1, 0, n, l, r, x);
        } else {
            int l, r;
            cin >> l >> r;
            update_isqrt(1, 0, n, l, r);
        }
    }
    return 0;
}