#include <bits/stdc++.h>
#define endl '\n'
 
using namespace std;
template<class T, class T2> inline void chkmax(T &x, const T2 &y) { if(x < y) x = y; }
template<class T, class T2> inline void chkmin(T &x, const T2 &y) { if(x > y) x = y; }
const int MAXN = (1 << 20);
 
int gcd(int a, int b) { return (a == 0 || b == 0) ? (a + b) : (__gcd(a, b)); }
 
struct segment_tree
{
    struct node
    {
        int64_t sum, lazy;
 
        node() {sum = 0; lazy = 0;}
        node(int64_t val)
        {
            sum = val;
            lazy = 0;
        }
    };
 
    node temp, broken;
 
    node merge(node l, node r)
    {
        temp.sum = l.sum + r.sum;
        temp.lazy = 0;
        return temp;
    }
 
    node tr[4 * MAXN];
 
    void push(int l, int r, int idx)
    {
        if(tr[idx].lazy)
        {
            tr[idx].sum = (r - l + 1) * tr[idx].lazy;
 
            if(l != r)
            {
                tr[2 * idx + 1].lazy = tr[idx].lazy;
                tr[2 * idx + 2].lazy = tr[idx].lazy;
            }
 
            tr[idx].lazy = 0;
        }
    }
 
    void init(int l, int r, int idx)
    {
        if(l == r)
        {
            tr[idx] = node(0);
            return;
        }
 
        int mid = (l + r) >> 1;
        init(l, mid, 2 * idx + 1);
        init(mid + 1, r, 2 * idx + 2);
 
        tr[idx] = merge(tr[2 * idx + 1], tr[2 * idx + 2]);
    }
 
    void update(int qL, int qR, int val, int l, int r, int idx)
    {
        push(l, r, idx);
 
        if(qL > r || l > qR)
            return;
 
        if(qL <= l && r <= qR)
        {
            tr[idx].lazy = val;
            push(l, r, idx);
            return;
        }
 
        int mid = (l + r) >> 1;
        update(qL, qR, val, l, mid, 2 * idx + 1);
        update(qL, qR, val, mid + 1, r, 2 * idx + 2);
 
        tr[idx] = merge(tr[2 * idx + 1], tr[2 * idx + 2]);
    }
 
    node query(int qL, int qR, int l, int r, int idx)
    {
        push(l, r, idx);
 
        if(l > qR || r < qL)
            return broken;
 
        if(qL <= l && r <= qR)
            return tr[idx];
 
        int mid = (l + r) >> 1;
        return merge(query(qL, qR, l, mid, 2 * idx + 1), query(qL, qR, mid + 1, r, 2 * idx + 2));
    }
};
 
segment_tree sum_t;
 
struct node
{
    int g;
    node() { g = 0; }
    node(int val) { g = val; }
};
 
int a[MAXN];
node temp, broken;
 
node merge(node l, node r)
{
    temp.g = gcd(l.g, r.g);
    return temp;
}
 
int bound_L[MAXN], bound_R[MAXN];
struct segment_tree_gcd
{
    node tr[4 * MAXN];
 
    void init(int l, int r, int idx)
    {
        bound_L[idx] = l;
        bound_R[idx] = r;
        if(l == r)
        {
            tr[idx] = node(a[l]);
            return;
        }
 
        int mid = (l + r) >> 1;
        init(l, mid, 2 * idx + 1);
        init(mid + 1, r, 2 * idx + 2);
 
        tr[idx] = merge(tr[2 * idx + 1], tr[2 * idx + 2]);
    }
 
    void update(int pos, int val, int l, int r, int idx)
    {
        if(l > pos || r < pos)
            return;
 
        if(l == r && l == pos)
        {
            tr[idx].g = val;
            return;
        }
 
        int mid = (l + r) >> 1;
        update(pos, val, l, mid, 2 * idx + 1);
        update(pos, val, mid + 1, r, 2 * idx + 2);
 
        tr[idx] = merge(tr[2 * idx + 1], tr[2 * idx + 2]);
    }
 
    void get_nodes(int qL, int qR, int l, int r, int idx, vector<int> &li)
    {
        if(l > qR || r < qL) return;
        if(qL <= l && r <= qR)
        {
            li.push_back(idx);
            return;
        }
 
        int mid = (l + r) >> 1;
        get_nodes(qL, qR, l, mid, 2 * idx + 1, li);
        get_nodes(qL, qR, mid + 1, r, 2 * idx + 2, li);
    }
 
    int get_left(int l, int r, int idx, int X)
    {
        if(l == r) return l;
 
        int mid = (l + r) >> 1, new_gcd = gcd(X, tr[2 * idx + 2].g);
        if(new_gcd == 1) return get_left(mid + 1, r, 2 * idx + 2, X);
        else return get_left(l, mid, 2 * idx + 1, new_gcd);
    }
 
    int get_left_same(int l, int r, int idx, int X)
    {
        if(l == r) return l;
 
        int mid = (l + r) >> 1, new_gcd = gcd(X, tr[2 * idx + 2].g);
        if(new_gcd != X) return get_left_same(mid + 1, r, 2 * idx + 2, X);
        else return get_left_same(l, mid, 2 * idx + 1, new_gcd);
    }
 
    int get_right(int l, int r, int idx, int X)
    {
        if(l == r) return l;
 
        int mid = (l + r) >> 1, new_gcd = gcd(X, tr[2 * idx + 1].g);
        if(new_gcd == 1) return get_right(l, mid, 2 * idx + 1, X);
        else return get_right(mid + 1, r, 2 * idx + 2, new_gcd);
    }
};
 
int n;
segment_tree_gcd t;
 
int get_left(int pos)
{
    vector<int> li;
    t.get_nodes(1, pos, 1, n, 0, li);
    reverse(li.begin(), li.end());
 
    int c_gcd = 0;
    for(int it: li)
    {
        int prv_gcd = c_gcd;
        c_gcd = gcd(c_gcd, t.tr[it].g);
        if(c_gcd == 1) return t.get_left(bound_L[it], bound_R[it], it, prv_gcd);
    }
 
    return 0;
}
 
int get_right(int pos)
{
    vector<int> li;
    t.get_nodes(pos, n, 1, n, 0, li);
 
    int c_gcd = 0;
    for(int it: li)
    {
        int prv_gcd = c_gcd;
        c_gcd = gcd(c_gcd, t.tr[it].g);
        if(c_gcd == 1) return t.get_right(bound_L[it], bound_R[it], it, prv_gcd);
    }
 
    return n + 1;
}
 
int get_left_equal(int pos, int G)
{    
    vector<int> li;
    t.get_nodes(1, pos, 1, n, 0, li);
    reverse(li.begin(), li.end());
 
    int c_gcd = G;
    for(int it: li)
    {
        int prv_gcd = c_gcd;
        c_gcd = gcd(c_gcd, t.tr[it].g);
        if(c_gcd < G) return t.get_left_same(bound_L[it], bound_R[it], it, prv_gcd);
    }
 
    return 0;
}
 
void update_value(int pos, int val)
{
    int L_pos = get_left(pos) + 1;
    if(a[pos] == 1) L_pos = pos;
    
    t.update(pos, val, 1, n, 0);
    sum_t.update(L_pos, pos, pos, 1, n, 0);
    a[pos] = val;
 
    int g = a[pos], curr = pos;
    while(g != 1 && curr > 0)
    {
        int j = get_left_equal(curr, g);
 
        int new_r_value = get_right(j + 1);
        t.update(pos, a[pos], 1, n, 0);
 
        sum_t.update(j + 1, curr, new_r_value, 1, n, 0);
        curr = j;
 
        if(curr > 0) g = gcd(g, a[curr]);
    }
}
 
void update_naive(int pos, int val)
{
    a[pos] = val;
    t.update(pos, val, 1, n, 0);
    for(int i = 1; i <= n; i++)
        sum_t.update(i, i, get_right(i), 1, n, 0);
}
 
int get_r_value(int pos) { return sum_t.query(pos, pos, 1, n, 0).sum; }
 
int q;
 
void read()
{
    cin >> n >> q; 
    for(int i = 1; i <= n; i++)
        cin >> a[i];
}
 
int64_t query(int L, int R)
{
    int64_t ans = 0;
 
    int low = L, high = R, mid, r = R + 1;
    while(low <= high)
    {
        mid = (low + high) >> 1;
        if(get_r_value(mid) > R)
            r = mid, high = mid - 1;
        else 
            low = mid + 1;
    }
 
    ans -= ((R + 1ll) * 1ll * (R)) / 2ll;
    ans += ((L - 1ll) * 1ll * (L)) / 2ll;
 
    ans += (R - r + 1ll) * 1ll * (R + 1ll);
    if(L < r) ans += sum_t.query(L, r - 1, 1, n, 0).sum;
 
    return ans;
}
 
void solve()
{
    t.init(1, n, 0);
    sum_t.init(1, n, 0);    
 
    for(int i = 1; i <= n; i++)
        update_value(i, a[i]);
        //update_naive(i, a[i]);
 
    while(q--)
    {
        int type;
        cin >> type;
 
        if(type == 1)
        {
            int pos, val;
            cin >> pos >> val;
            update_value(pos, val);
            //update_naive(pos, val);
        }
        else
        {
            int l, r;
            cin >> l >> r;
            cout << query(l, r) << endl;
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    read();
    solve();
    return 0;
}