#include using namespace std; using ll = long long; template struct lazy_segtree { static_assert(std::is_convertible_v>, "op must work as S(S, S)"); static_assert(std::is_convertible_v>, "e must work as S()"); static_assert(std::is_convertible_v>, "mapping must work as F(F, S)"); static_assert(std::is_convertible_v>, "compostiion must work as F(F, F)"); static_assert(std::is_convertible_v>, "id must work as F()"); public: lazy_segtree(): lazy_segtree(0) {} explicit lazy_segtree(int n): lazy_segtree(std::vector(n, e())) {} explicit lazy_segtree(const std::vector& v): _n(int(v.size())) { size = (int)bit_ceil((unsigned int)(_n)); log = countr_zero((unsigned int)size); d = std::vector(2 * size, e()); lz = std::vector(size, id()); for(int i = 0; i < _n; i++) { d[size + i] = v[i]; } for(int i = size - 1; i >= 1; i--) { update(i); } } void set(int p, S x) { assert(0 <= p && p < _n); p += size; for(int i = log; i >= 1; i--) { push(p >> i); } d[p] = x; for(int i = 1; i <= log; i++) { update(p >> i); } } S get(int p) { assert(0 <= p && p < _n); p += size; for(int i = log; i >= 1; i--) { push(p >> i); } return d[p]; } S prod(int l, int r) { assert(0 <= l && l <= r && r <= _n); if(l == r) { return e(); } l += size; r += size; for(int i = log; i >= 1; i--) { if(((l >> i) << i) != l) { push(l >> i); } if(((r >> i) << i) != r) { push((r - 1) >> i); } } S sml = e(), smr = e(); while(l < r) { if(l & 1) { sml = op(sml, d[l++]); } if(r & 1) { smr = op(d[--r], smr); } l >>= 1; r >>= 1; } return op(sml, smr); } S all_prod() { return d[1]; } void apply(int p, F f) { assert(0 <= p && p < _n); p += size; for(int i = log; i >= 1; i--) { push(p >> i); } d[p] = mapping(f, d[p]); for(int i = 1; i <= log; i++) { update(p >> i); } } void apply(int l, int r, F f) { assert(0 <= l && l <= r && r <= _n); if(l == r) return; l += size; r += size; for(int i = log; i >= 1; i--) { if(((l >> i) << i) != l) { push(l >> i); } if(((r >> i) << i) != r) { push((r - 1) >> i); } } { int l2 = l, r2 = r; while(l < r) { if(l & 1) { all_apply(l++, f); } if(r & 1) { all_apply(--r, f); } l >>= 1; r >>= 1; } l = l2; r = r2; } for(int i = 1; i <= log; i++) { if(((l >> i) << i) != l) { update(l >> i); } if(((r >> i) << i) != r) { update((r - 1) >> i); } } } template int max_right(int l) { return max_right(l, [](S x) { return g(x); }); } template int max_right(int l, G g) { assert(0 <= l && l <= _n); assert(g(e())); if(l == _n) { return _n; } l += size; for(int i = log; i >= 1; i--) { push(l >> i); } S sm = e(); do { while(l % 2 == 0) l >>= 1; if(!g(op(sm, d[l]))) { while(l < size) { push(l); l = (2 * l); if(g(op(sm, d[l]))) { sm = op(sm, d[l]); l++; } } return l - size; } sm = op(sm, d[l]); l++; } while((l & -l) != l); return _n; } template int min_left(int r) { return min_left(r, [](S x) { return g(x); }); } template int min_left(int r, G g) { assert(0 <= r && r <= _n); assert(g(e())); if(r == 0) { return 0; } r += size; for(int i = log; i >= 1; i--) { push((r - 1) >> i); } S sm = e(); do { r--; while(r > 1 && (r % 2)) r >>= 1; if(!g(op(d[r], sm))) { while(r < size) { push(r); r = (2 * r + 1); if(g(op(d[r], sm))) { sm = op(d[r], sm); r--; } } return r + 1 - size; } sm = op(d[r], sm); } while((r & -r) != r); return 0; } private: int _n, size, log; std::vector d; std::vector lz; void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); } void all_apply(int k, F f) { d[k] = mapping(f, d[k]); if(k < size) { lz[k] = composition(f, lz[k]); if(d[k].fail) { push(k), update(k); } } } void push(int k) { all_apply(2 * k, lz[k]); all_apply(2 * k + 1, lz[k]); lz[k] = id(); } }; // constexpr ll INF = 1LL << 30; // struct S { // ll max, lcm, sz, sum; // bool fail; // S(): max(0), lcm(1), sz(0), sum(0), fail(false) {} // S(ll x, ll sz = 1): max(x), lcm(x), sz(sz), sum(x * sz), fail(false) {} // }; // struct F { // ll g, upd; // F(): g(0), upd(0) {} // F(ll g, ll upd): g(g), upd(upd) {} // static F gcd(ll x) noexcept { return F(x, 0); } // static F update(ll x) noexcept { return F(0, x); } // }; // S op(S l, S r) { // if(!r.sz) { return l; } // if(!l.sz) { return r; } // S ret; // ret.max = std::max(l.max, r.max); // ret.sum = l.sum + r.sum; // ret.lcm = min(INF, std::lcm(l.lcm, r.lcm)); // ret.sz = l.sz + r.sz; // return ret; // } // S e() { return S(); } // S fx(F f, S x) { // if(x.fail) { return x; } // if(f.upd) { return S(f.upd, x.sz); } // if(f.g) { // if(x.sz == 1) { return S(gcd(x.max, f.g)); } // else if(x.lcm == INF || f.g % x.lcm) { x.fail = true; } // } // return x; // } // F fg(F f, F g) { // if(f.upd) { return F::update(f.upd); } // else if(g.upd) { return F::update(gcd(f.g, g.upd)); } // else { return F::gcd(gcd(f.g, g.g)); } // } // F id() { return F(); } ll INF = 2e9; struct S { int max_val; int lcm; int len; ll sum; bool fail; }; S e() { return {0, 1, 0, 0, false}; } S apply_reset(S original, int x) { return {x, x, original.len, (ll)original.len * x, false}; } S op(S l, S r) { if(r.len == 0) return l; if(l.len == 0) return r; S ret = e(); ret.max_val = max(l.max_val, r.max_val); ret.lcm = min(INF, (ll)l.lcm * r.lcm / __gcd(l.lcm, r.lcm)); ret.len = l.len + r.len; ret.sum = l.sum + r.sum; return ret; } struct F { int dogcd; int reset; }; F id() { return {0, 0}; } S fx(F f, S x) { if(x.fail) return x; assert(!((f.reset > 0) && (f.dogcd > 0))); if(f.reset > 0) { return apply_reset(x, f.reset); } if(f.dogcd > 0) { if((ll)x.len * x.max_val == x.sum) { return apply_reset(x, __gcd(f.dogcd, x.max_val)); } if(x.lcm == INF || f.dogcd % x.lcm > 0) { x.fail = 1; return x; } } return x; } F fg(F g, F f) { if(g.reset) { return {0, g.reset}; } if(f.reset) { return {0, __gcd(g.dogcd, f.reset)}; } return {__gcd(g.dogcd, f.dogcd), 0}; } int main() { ios::sync_with_stdio(false); cin.tie(0); ll N, Q; cin >> N >> Q; vector A(N); for(ll i = 0; i < N; i++) { ll a; cin >> a; A[i] = apply_reset({0, 1, 1, 0}, a); } lazy_segtree seg(A); while(Q--) { ll type, l, r, x; cin >> type >> l >> r; l--; if(type <= 2) { cin >> x; } if(type == 1) { seg.apply(l, r, {0, x}); } if(type == 2) { seg.apply(l, r, {x, 0}); } if(type == 3) { cout << seg.prod(l, r).max_val << "\n"; } if(type == 4) { cout << seg.prod(l, r).sum << "\n"; } } }