// I also thought that there was a small chance that she likes me back.
#include <bits/stdc++.h>
using namespace std;
// Do you think you'll ever remember me someday, or will I just fade away from your memory?
#define LIFESUCK ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#define str string
#define mll map<ll, ll>
#define vll vector<ll>
#define pll pair<ll, ll>
#define fi first
#define se second
#define all(c) c.begin(), c.end()
#define pb push_back
#define sz(s) s.size()
#define debug cout << "I Love You\n";
#define fu(i, a, b) for (ll i = a; i <= b; i++)
#define fd(i, b, a) for (ll i = b; i >= a; i--)
#define Bitc(msk, j) ((msk >> j) & 1)
#define _log(x) 63 - __builtin_clzll(x)
#define LoveTime chrono::steady_clock::now().time_since_epoch().count()
const ll Mod = 998244353;
const ll inf = (1ll << 30);
const ll lnf = (1ll << 60);
// When time passes and things change... will you still remember someone like me?
int64_t add(ll& a, ll b) {
a += b;
if (a >= Mod) a %= Mod;
while (a < 0) a += Mod;
return a;
}
int64_t mul(ll a, ll b) {
a = 1ll * a * b % Mod;
return a;
}
template <class X, class Y>
bool minimize(X& x, Y y) {
X eps = 1e-9;
if (x > y + eps) {
x = y;
return 1;
}
return 0;
}
template <class X, class Y>
bool maximize(X& x, Y y) {
X eps = 1e-9;
if (x + eps < y) {
x = y;
return 1;
}
return 0;
}
// I wonder… will I just become a distant memory to you one day?
#define mxn 200'007
ll n, q, g[mxn];
vll graph[mxn];
struct Node {
ll ans, gcd;
vector<pll> pref, suf;
Node() {
ans = 0; gcd = 0;
pref.clear(); suf.clear();
}
void compress(vector<pll>& c) {
mll mp;
vector<pll> res;
for(auto&[i, j]: c) mp[i] += j;
for(auto&[i, j]: mp) res.pb({i, j});
swap(c, res);
}
Node friend operator+(const Node&Lft, const Node&Rgh) {
Node res;
res.gcd = __gcd(Lft.gcd, Rgh.gcd);
res.pref = Lft.pref;
res.suf = Rgh.suf;
for(auto&[x, cnt]: Rgh.pref) res.pref.pb({__gcd(Lft.gcd, x), cnt});
for(auto&[x, cnt]: Lft.suf) res.suf.pb({__gcd(Rgh.gcd, x), cnt});
res.ans = Lft.ans + Rgh.ans;
for(auto&[a, cnt1]: Lft.suf) for(auto&[b, cnt2]: Rgh.pref)
if(__gcd(a, b) == 1) res.ans += (cnt1 * cnt2);
res.compress(res.pref);
res.compress(res.suf);
return res;
}
};
struct SegmentTree {
vector<Node> f;
SegmentTree(ll _n = 0): f(4 * _n + 7, Node()) {}
void update(ll id, ll l, ll r, ll pos, ll val) {
if(r < pos || pos < l) return;
if(l == r) {
f[id].pref.clear();
f[id].suf.clear();
f[id].ans = (val == 1);
f[id].gcd = val;
f[id].pref.pb({val, 1});
f[id].suf.pb({val, 1});
return;
}
ll mid = l + (r - l) / 2;
update(id << 1, l, mid, pos, val);
update(id << 1 | 1, mid + 1, r, pos, val);
f[id] = f[id << 1] + f[id << 1 | 1];
}
Node get(ll id, ll l, ll r, ll u, ll v) {
if(r < u || v < l) return Node();
if(u <= l && r <= v) return f[id];
ll mid = l + (r - l) / 2;
Node Lft = get(id << 1, l, mid, u, v);
Node Rgh = get(id << 1 | 1, mid + 1, r, u, v);
return Lft + Rgh;
}
};
// The world is still beautiful, only it’s a pity that you are no longer among the living.
void lovesper(const ll& TestCase) {
cin >> n >> q;
SegmentTree st(n);
fu(i, 1, n) {
ll x; cin >> x;
st.update(1, 1, n, i, x);
}
fu(qst, 1, q) {
ll o; cin >> o;
if(o == 1) {
ll pos, x; cin >> pos >> x;
st.update(1, 1, n, pos, x);
} else {
ll l, r; cin >> l >> r;
ll mie = (r - l + 1);
cout << mie * (mie + 1) / 2 - st.get(1, 1, n, l, r).ans << '\n';
}
}
}
// In the future, each of us will have our own path..
// ...But no matter where we go, we will always be a beautiful part of each other’s memories.
signed main() {
LIFESUCK
#define name "lovesper"
// freopen(name".inp", "r", stdin);
// freopen(name".out", "w", stdout);
ll Test = 1;
// cin >> Test;
fu(i, 1, Test) {
lovesper(i);
if (i < Test) cout << '\n';
}
return 0;
}
