c652

/* c652              */
/* AC (0.2s, 18.4MB) */
#pragma warning( disable : 4996 )
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

using int16 = short;
using uint16 = unsigned short;
using uint = unsigned int;
using int64 = long long;
using uint64 = unsigned long long;

/* main code */
constexpr int MAXN = 300001;

int N, Q, ql, qr;

uint64 arr[MAXN], Sum[MAXN * 4], Max[MAXN * 4];
uint64 initMax(int l, int r, int nowNode)
{
    if (l == r)
    {
        Max[nowNode] = arr[l];
        return arr[l];
    }

    int mid = (l + r) >> 1;
    Max[nowNode] = max<uint64>(initMax(l, mid, nowNode << 1), initMax(mid + 1, r, nowNode << 1 | 1));

    return Max[nowNode];
}
uint64 initSum(int l, int r, int nowNode)
{
    if (l == r)
    {
        Sum[nowNode] = arr[l];
        return arr[l];
    }

    int mid = (l + r) >> 1;
    Sum[nowNode] = initSum(l, mid, nowNode << 1) + initSum(mid + 1, r, nowNode << 1 | 1);

    return Sum[nowNode];
}

void updata_range(int l, int r, int nowNode)
{
    if (Max[nowNode] <= 1) return;

    uint64 tmp;
    int mid;
    if (l == r)
    {
        tmp = arr[l] - (uint64)sqrt(arr[l]);
        Sum[nowNode >> 1] -= tmp;
        arr[l] -= tmp;
        Sum[nowNode] = Max[nowNode] = arr[l];
        return;
    }
    tmp = Sum[nowNode];
    mid = (l + r) >> 1;
    if (ql <= mid) updata_range(l, mid, nowNode << 1);
    if (qr >= mid + 1) updata_range(mid + 1, r, nowNode << 1 | 1);

    Max[nowNode] = max<uint64>(Max[nowNode << 1], Max[nowNode << 1 | 1]);
    Sum[nowNode >> 1] -= (tmp - Sum[nowNode]);
}

uint64 query_Sum(int l, int r, int nowNode)
{
    if (ql <= l && qr >= r) return Sum[nowNode];
    int mid = (l + r) >> 1;

    uint64 res = 0;
    if (ql <= mid) res += query_Sum(l, mid, nowNode << 1);
    if (qr >= mid + 1) res += query_Sum(mid + 1, r, nowNode << 1 | 1);

    return res;
}

int main()
{
    scanf("%d %d", &N, &Q);
    for (int i = 1; i <= N; ++i)
        scanf("%llu", arr + i);
    initMax(1, N, 1);
    initSum(1, N, 1);
    for (int i = 0, op; i < Q; ++i)
    {
        scanf("%d %d %d", &op, &ql, &qr);
        if (op == 0)
            printf("%llu\n", query_Sum(1, N, 1));
        else
            updata_range(1, N, 1);
    }

    return 0;
}