This documentation is automatically generated by online-judge-tools/verification-helper
#define PROBLEM "https://judge.yosupo.jp/problem/point_set_range_composite"
#include <bits/stdc++.h>
using namespace std;
#include "../SegTree.h"
#include "../../Math/modint.h"
#include "../../buffered_reader.h"
using modular = ModInt<998244353>;
struct Func {
modular a, b;
};
Func op(Func l, Func r) {
return Func{
l.a * r.a,
r.a * l.b + r.b
};
}
Func e() {
return Func{1, 0};
}
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
int n = IO::get<int>();
int q = IO::get<int>();
vector<Func> funcs(n);
for (auto& f : funcs) {
int a = IO::get<int>();
int b = IO::get<int>();
f = {a, b};
}
SegTree<Func, op, e> seg_tree(funcs);
while (q--) {
int typ = IO::get<int>();
if (typ == 0) {
int pos = IO::get<int>();
int a = IO::get<int>();
int b = IO::get<int>();
seg_tree.set(pos, {a, b});
} else {
int l = IO::get<int>();
int r = IO::get<int>();
auto f = seg_tree.prod(l, r);
modular x(IO::get<int>());
cout << f.a * x + f.b << '\n';
}
}
return 0;
}
#line 1 "DataStructure/test/segment_tree_pointsetrangecomposite.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/point_set_range_composite"
#include <bits/stdc++.h>
using namespace std;
#line 1 "DataStructure/SegTree.h"
// SegTree, copied from AtCoder library {{{
// AtCoder doc: https://atcoder.github.io/ac-library/master/document_en/segtree.html
//
// Notes:
// - Index of elements from 0 -> n-1
// - Range queries are [l, r-1]
//
// Tested:
// - (binary search) https://atcoder.jp/contests/practice2/tasks/practice2_j
// - https://oj.vnoi.info/problem/gss
// - https://oj.vnoi.info/problem/nklineup
// - (max_right & min_left for delete position queries) https://oj.vnoi.info/problem/segtree_itstr
// - https://judge.yosupo.jp/problem/point_add_range_sum
// - https://judge.yosupo.jp/problem/point_set_range_composite
int ceil_pow2(int n) {
int x = 0;
while ((1U << x) < (unsigned int)(n)) x++;
return x;
}
template<
class T, // data type for nodes
T (*op) (T, T), // operator to combine 2 nodes
T (*e)() // identity element
>
struct SegTree {
SegTree() : SegTree(0) {}
explicit SegTree(int n) : SegTree(vector<T> (n, e())) {}
explicit SegTree(const vector<T>& v) : _n((int) v.size()) {
log = ceil_pow2(_n);
size = 1<<log;
d = vector<T> (2*size, e());
for (int i = 0; i < _n; i++) d[size+i] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}
// 0 <= p < n
void set(int p, T x) {
assert(0 <= p && p < _n);
p += size;
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
// 0 <= p < n
T get(int p) const {
assert(0 <= p && p < _n);
return d[p + size];
}
// Get product in range [l, r-1]
// 0 <= l <= r <= n
// For empty segment (l == r) -> return e()
T prod(int l, int r) const {
assert(0 <= l && l <= r && r <= _n);
T sml = e(), smr = e();
l += size;
r += size;
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);
}
T all_prod() const {
return d[1];
}
// Binary search on SegTree to find largest r:
// f(op(a[l] .. a[r-1])) = true (assuming empty array is always true)
// f(op(a[l] .. a[r])) = false (assuming op(..., a[n]), which is out of bound, is always false)
template <bool (*f)(T)> int max_right(int l) const {
return max_right(l, [](T x) { return f(x); });
}
template <class F> int max_right(int l, F f) const {
assert(0 <= l && l <= _n);
assert(f(e()));
if (l == _n) return _n;
l += size;
T sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!f(op(sm, d[l]))) {
while (l < size) {
l = (2 * l);
if (f(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;
}
// Binary search on SegTree to find smallest l:
// f(op(a[l] .. a[r-1])) = true (assuming empty array is always true)
// f(op(a[l-1] .. a[r-1])) = false (assuming op(a[-1], ..), which is out of bound, is always false)
template <bool (*f)(T)> int min_left(int r) const {
return min_left(r, [](T x) { return f(x); });
}
template <class F> int min_left(int r, F f) const {
assert(0 <= r && r <= _n);
assert(f(e()));
if (r == 0) return 0;
r += size;
T sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!f(op(d[r], sm))) {
while (r < size) {
r = (2 * r + 1);
if (f(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;
vector<T> d;
void update(int k) {
d[k] = op(d[2*k], d[2*k+1]);
}
};
// }}}
// SegTree examples {{{
// Examples: Commonly used SegTree ops: max / min / sum
struct MaxSegTreeOp {
static int op(int x, int y) {
return max(x, y);
}
static int e() {
return INT_MIN;
}
};
struct MinSegTreeOp {
static int op(int x, int y) {
return min(x, y);
}
static int e() {
return INT_MAX;
}
};
struct SumSegTreeOp {
static long long op(long long x, long long y) {
return x + y;
}
static long long e() {
return 0;
}
};
// using STMax = SegTree<int, MaxSegTreeOp::op, MaxSegTreeOp::e>;
// using STMin = SegTree<int, MinSegTreeOp::op, MinSegTreeOp::e>;
// using STSum = SegTree<int, SumSegTreeOp::op, SumSegTreeOp::e>;
// }}}
#line 1 "Math/modint.h"
// ModInt {{{
template<int MD> struct ModInt {
using ll = long long;
int x;
constexpr ModInt() : x(0) {}
constexpr ModInt(ll v) { _set(v % MD + MD); }
constexpr static int mod() { return MD; }
constexpr explicit operator bool() const { return x != 0; }
constexpr ModInt operator + (const ModInt& a) const {
return ModInt()._set((ll) x + a.x);
}
constexpr ModInt operator - (const ModInt& a) const {
return ModInt()._set((ll) x - a.x + MD);
}
constexpr ModInt operator * (const ModInt& a) const {
return ModInt()._set((ll) x * a.x % MD);
}
constexpr ModInt operator / (const ModInt& a) const {
return ModInt()._set((ll) x * a.inv().x % MD);
}
constexpr ModInt operator - () const {
return ModInt()._set(MD - x);
}
constexpr ModInt& operator += (const ModInt& a) { return *this = *this + a; }
constexpr ModInt& operator -= (const ModInt& a) { return *this = *this - a; }
constexpr ModInt& operator *= (const ModInt& a) { return *this = *this * a; }
constexpr ModInt& operator /= (const ModInt& a) { return *this = *this / a; }
friend constexpr ModInt operator + (ll a, const ModInt& b) {
return ModInt()._set(a % MD + b.x);
}
friend constexpr ModInt operator - (ll a, const ModInt& b) {
return ModInt()._set(a % MD - b.x + MD);
}
friend constexpr ModInt operator * (ll a, const ModInt& b) {
return ModInt()._set(a % MD * b.x % MD);
}
friend constexpr ModInt operator / (ll a, const ModInt& b) {
return ModInt()._set(a % MD * b.inv().x % MD);
}
constexpr bool operator == (const ModInt& a) const { return x == a.x; }
constexpr bool operator != (const ModInt& a) const { return x != a.x; }
friend std::istream& operator >> (std::istream& is, ModInt& other) {
ll val; is >> val;
other = ModInt(val);
return is;
}
constexpr friend std::ostream& operator << (std::ostream& os, const ModInt& other) {
return os << other.x;
}
constexpr ModInt pow(ll k) const {
ModInt ans = 1, tmp = x;
while (k) {
if (k & 1) ans *= tmp;
tmp *= tmp;
k >>= 1;
}
return ans;
}
constexpr ModInt inv() const {
if (x < 1000111) {
_precalc(1000111);
return invs[x];
}
int a = x, b = MD, ax = 1, bx = 0;
while (b) {
int q = a/b, t = a%b;
a = b; b = t;
t = ax - bx*q;
ax = bx; bx = t;
}
assert(a == 1);
if (ax < 0) ax += MD;
return ax;
}
static std::vector<ModInt> factorials, inv_factorials, invs;
constexpr static void _precalc(int n) {
if (factorials.empty()) {
factorials = {1};
inv_factorials = {1};
invs = {0};
}
if (n > MD) n = MD;
int old_sz = factorials.size();
if (n <= old_sz) return;
factorials.resize(n);
inv_factorials.resize(n);
invs.resize(n);
for (int i = old_sz; i < n; ++i) factorials[i] = factorials[i-1] * i;
inv_factorials[n-1] = factorials.back().pow(MD - 2);
for (int i = n - 2; i >= old_sz; --i) inv_factorials[i] = inv_factorials[i+1] * (i+1);
for (int i = n-1; i >= old_sz; --i) invs[i] = inv_factorials[i] * factorials[i-1];
}
static int get_primitive_root() {
static int primitive_root = 0;
if (!primitive_root) {
primitive_root = [&]() {
std::set<int> fac;
int v = MD - 1;
for (ll i = 2; i * i <= v; i++)
while (v % i == 0) fac.insert(i), v /= i;
if (v > 1) fac.insert(v);
for (int g = 1; g < MD; g++) {
bool ok = true;
for (auto i : fac)
if (ModInt(g).pow((MD - 1) / i) == 1) {
ok = false;
break;
}
if (ok) return g;
}
return -1;
}();
}
return primitive_root;
}
static ModInt C(int n, int k) {
_precalc(n + 1);
return factorials[n] * inv_factorials[k] * inv_factorials[n-k];
}
private:
// Internal, DO NOT USE.
// val must be in [0, 2*MD)
constexpr inline __attribute__((always_inline)) ModInt& _set(ll v) {
x = v >= MD ? v - MD : v;
return *this;
}
};
template <int MD> std::vector<ModInt<MD>> ModInt<MD>::factorials = {1};
template <int MD> std::vector<ModInt<MD>> ModInt<MD>::inv_factorials = {1};
template <int MD> std::vector<ModInt<MD>> ModInt<MD>::invs = {0};
// }}}
#line 1 "buffered_reader.h"
// Buffered reader {{{
namespace IO {
const int BUFSIZE = 1<<14;
char buf[BUFSIZE + 1], *inp = buf;
bool reacheof;
char get_char() {
if (!*inp && !reacheof) {
memset(buf, 0, sizeof buf);
int tmp = fread(buf, 1, BUFSIZE, stdin);
if (tmp != BUFSIZE) reacheof = true;
inp = buf;
}
return *inp++;
}
template<typename T>
T get() {
int neg = 0;
T res = 0;
char c = get_char();
while (!std::isdigit(c) && c != '-' && c != '+') c = get_char();
if (c == '+') { neg = 0; }
else if (c == '-') { neg = 1; }
else res = c - '0';
c = get_char();
while (std::isdigit(c)) {
res = res * 10 + (c - '0');
c = get_char();
}
return neg ? -res : res;
}
};
// Helper methods
int ri() {
return IO::get<int>();
}
// }}}
#line 9 "DataStructure/test/segment_tree_pointsetrangecomposite.test.cpp"
using modular = ModInt<998244353>;
struct Func {
modular a, b;
};
Func op(Func l, Func r) {
return Func{
l.a * r.a,
r.a * l.b + r.b
};
}
Func e() {
return Func{1, 0};
}
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
int n = IO::get<int>();
int q = IO::get<int>();
vector<Func> funcs(n);
for (auto& f : funcs) {
int a = IO::get<int>();
int b = IO::get<int>();
f = {a, b};
}
SegTree<Func, op, e> seg_tree(funcs);
while (q--) {
int typ = IO::get<int>();
if (typ == 0) {
int pos = IO::get<int>();
int a = IO::get<int>();
int b = IO::get<int>();
seg_tree.set(pos, {a, b});
} else {
int l = IO::get<int>();
int r = IO::get<int>();
auto f = seg_tree.prod(l, r);
modular x(IO::get<int>());
cout << f.a * x + f.b << '\n';
}
}
return 0;
}