This documentation is automatically generated by online-judge-tools/verification-helper
#define PROBLEM "https://judge.yosupo.jp/problem/range_affine_range_sum"
#include <iostream>
#include <vector>
#include "../../data_structure/lazysegtree.hpp"
#include "../../template/template.hpp"
#include "../../utility/modint.hpp"
using namespace lib;
using mint = modint998244353;
struct S {
mint a;
int size;
};
struct F {
mint a, b;
F(mint a, mint b) : a(a), b(b) {}
};
S op(S l, S r) {
return S{l.a + r.a, l.size + r.size};
}
S e() {
return S{0, 0};
}
S mapping(F l, S r) {
return S{r.a * l.a + (mint)r.size * l.b, r.size};
}
F composition(F l, F r) {
return F{r.a * l.a, r.b * l.a + l.b};
}
F id() {
return F{1, 0};
}
int main() {
int n, q;
std::cin >> n >> q;
std::vector<S> v(n);
for (int i = 0; i < n; i++) {
int a;
std::cin >> a;
v[i] = {a, 1};
}
lazysegtree<S, op, e, F, mapping, composition, id> seg(v);
while (q--) {
int t;
std::cin >> t;
if (t == 0) {
int l, r, b, c;
std::cin >> l >> r >> b >> c;
seg.apply(l, r, F(b, c));
} else {
int l, r;
std::cin >> l >> r;
std::cout << seg.prod(l, r).a.val() << std::endl;
}
}
}
#line 1 "test/data_structure/Range_Affine_Range_Sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/range_affine_range_sum"
#include <iostream>
#include <vector>
#line 2 "data_structure/lazysegtree.hpp"
#line 2 "template/template.hpp"
#include <bits/stdc++.h>
#define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
#define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--)
#define all(v) v.begin(), v.end()
using ll = long long;
using ld = long double;
using ull = unsigned long long;
template <typename T> bool chmin(T &a, const T &b) {
if (a <= b) return false;
a = b;
return true;
}
template <typename T> bool chmax(T &a, const T &b) {
if (a >= b) return false;
a = b;
return true;
}
namespace lib {
using namespace std;
} // namespace lib
// using namespace lib;
#line 4 "data_structure/lazysegtree.hpp"
namespace lib {
template <class S, S (*op)(S, S), S (*e)(), class F, S (*mapping)(F, S),
F (*composition)(F, F), F (*id)()>
struct lazysegtree {
private:
int n, lg2, sz;
std::vector<S> d;
std::vector<F> lz;
void update(int i) {
d[i] = op(d[2 * i], d[2 * i + 1]);
}
void all_apply(int i, F f) {
d[i] = mapping(f, d[i]);
if (i < sz) lz[i] = composition(f, lz[i]);
}
void push(int i) {
all_apply(2 * i, lz[i]);
all_apply(2 * i + 1, lz[i]);
lz[i] = id();
}
public:
lazysegtree(int _n) : lazysegtree(std::vector<S>(_n, e())) {}
lazysegtree(const std::vector<S> &v) : n(v.size()) {
lg2 = 0;
while ((1 << lg2) < n) lg2++;
sz = 1 << lg2;
d = std::vector<S>(2 * sz, e());
lz = std::vector<F>(2 * sz, id());
for (int i = 0; i < n; i++) d[sz + i] = v[i];
for (int i = sz - 1; i >= 1; i--) update(i);
}
void set(int p, S x) {
assert(0 <= p && p < n);
p += sz;
rrep(i, 1, lg2 + 1) push(p >> i);
d[p] = x;
rep(i, 1, lg2 + 1) update(p >> i);
}
S get(int p) {
assert(0 <= p && p < n);
p += sz;
rrep(i, 1, lg2 + 1) 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 += sz;
r += sz;
rrep(i, 1, lg2 + 1) {
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 += sz;
rrep(i, 1, lg2 + 1) push(p >> i);
d[p] = mapping(f, d[p]);
rep(i, 1, lg2 + 1) update(p >> i);
}
void apply(int l, int r, F f) {
assert(0 <= l && l <= r && r <= n);
if (l == r) return;
l += sz;
r += sz;
rrep(i, 1, lg2 + 1) {
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;
}
rep(i, 1, lg2 + 1) {
if (((l >> i) << i) != l) update(l >> i);
if (((r >> i) << i) != r) update((r - 1) >> i);
}
}
template <class G> int max_right(int l, G g) {
assert(0 <= l && l <= n);
assert(g(e()));
if (l == n) return n;
l += sz;
for (int i = lg2; i >= 1; i--) push(l >> i);
S sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!g(op(sm, d[l]))) {
while (l < sz) {
push(l);
l = (2 * l);
if (g(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - sz;
}
sm = op(sm, d[l]);
l++;
} while ((l & -l) != l);
return n;
}
template <class G> int min_left(int r, G g) {
assert(0 <= r && r <= n);
assert(g(e()));
if (r == 0) return 0;
r += sz;
for (int i = lg2; 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 < sz) {
push(r);
r = (2 * r + 1);
if (g(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - sz;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
};
} // namespace lib
#line 2 "utility/modint.hpp"
#line 4 "utility/modint.hpp"
namespace lib {
template <ll m> struct modint {
using mint = modint;
ll a;
modint(ll x = 0) : a((x % m + m) % m) {}
static constexpr ll mod() {
return m;
}
ll val() const {
return a;
}
ll& val() {
return a;
}
mint pow(ll n) const {
mint res = 1;
mint x = a;
while (n) {
if (n & 1) res *= x;
x *= x;
n >>= 1;
}
return res;
}
mint inv() const {
return pow(m - 2);
}
mint& operator+=(const mint rhs) {
a += rhs.a;
if (a >= m) a -= m;
return *this;
}
mint& operator-=(const mint rhs) {
if (a < rhs.a) a += m;
a -= rhs.a;
return *this;
}
mint& operator*=(const mint rhs) {
a = a * rhs.a % m;
return *this;
}
mint& operator/=(mint rhs) {
*this *= rhs.inv();
return *this;
}
friend mint operator+(const mint& lhs, const mint& rhs) {
return mint(lhs) += rhs;
}
friend mint operator-(const mint& lhs, const mint& rhs) {
return mint(lhs) -= rhs;
}
friend mint operator*(const mint& lhs, const mint& rhs) {
return mint(lhs) *= rhs;
}
friend mint operator/(const mint& lhs, const mint& rhs) {
return mint(lhs) /= rhs;
}
friend bool operator==(const modint &lhs, const modint &rhs) {
return lhs.a == rhs.a;
}
friend bool operator!=(const modint &lhs, const modint &rhs) {
return !(lhs == rhs);
}
mint operator+() const {
return *this;
}
mint operator-() const {
return mint() - *this;
}
};
using modint998244353 = modint<998244353>;
using modint1000000007 = modint<1'000'000'007>;
} // namespace lib
#line 9 "test/data_structure/Range_Affine_Range_Sum.test.cpp"
using namespace lib;
using mint = modint998244353;
struct S {
mint a;
int size;
};
struct F {
mint a, b;
F(mint a, mint b) : a(a), b(b) {}
};
S op(S l, S r) {
return S{l.a + r.a, l.size + r.size};
}
S e() {
return S{0, 0};
}
S mapping(F l, S r) {
return S{r.a * l.a + (mint)r.size * l.b, r.size};
}
F composition(F l, F r) {
return F{r.a * l.a, r.b * l.a + l.b};
}
F id() {
return F{1, 0};
}
int main() {
int n, q;
std::cin >> n >> q;
std::vector<S> v(n);
for (int i = 0; i < n; i++) {
int a;
std::cin >> a;
v[i] = {a, 1};
}
lazysegtree<S, op, e, F, mapping, composition, id> seg(v);
while (q--) {
int t;
std::cin >> t;
if (t == 0) {
int l, r, b, c;
std::cin >> l >> r >> b >> c;
seg.apply(l, r, F(b, c));
} else {
int l, r;
std::cin >> l >> r;
std::cout << seg.prod(l, r).a.val() << std::endl;
}
}
}