// #define _GLIBCXX_DEBUG // #pragma GCC optimize("O2,unroll-loops") #include using namespace std; #define rep(i, n) for (int i = 0; i < int(n); i++) #define per(i, n) for (int i = (n)-1; 0 <= i; i--) #define rep2(i, l, r) for (int i = (l); i < int(r); i++) #define per2(i, l, r) for (int i = (r)-1; int(l) <= i; i--) #define each(e, v) for (auto &e : v) #define MM << " " << #define pb push_back #define eb emplace_back #define all(x) begin(x), end(x) #define rall(x) rbegin(x), rend(x) #define sz(x) (int)x.size() template void print(const vector &v, T x = 0) { int n = v.size(); for (int i = 0; i < n; i++) cout << v[i] + x << (i == n - 1 ? '\n' : ' '); if (v.empty()) cout << '\n'; } using ll = long long; using pii = pair; using pll = pair; template bool chmax(T &x, const T &y) { return (x < y) ? (x = y, true) : false; } template bool chmin(T &x, const T &y) { return (x > y) ? (x = y, true) : false; } template using minheap = std::priority_queue, std::greater>; template using maxheap = std::priority_queue; template int lb(const vector &v, T x) { return lower_bound(begin(v), end(v), x) - begin(v); } template int ub(const vector &v, T x) { return upper_bound(begin(v), end(v), x) - begin(v); } template void rearrange(vector &v) { sort(begin(v), end(v)); v.erase(unique(begin(v), end(v)), end(v)); } // __int128_t gcd(__int128_t a, __int128_t b) { // if (a == 0) // return b; // if (b == 0) // return a; // __int128_t cnt = a % b; // while (cnt != 0) { // a = b; // b = cnt; // cnt = a % b; // } // return b; // } struct Union_Find_Tree { vector data; const int n; int cnt; Union_Find_Tree(int n) : data(n, -1), n(n), cnt(n) {} int root(int x) { if (data[x] < 0) return x; return data[x] = root(data[x]); } int operator[](int i) { return root(i); } bool unite(int x, int y) { x = root(x), y = root(y); if (x == y) return false; // if (data[x] > data[y]) swap(x, y); data[x] += data[y], data[y] = x; cnt--; return true; } int size(int x) { return -data[root(x)]; } int count() { return cnt; }; bool same(int x, int y) { return root(x) == root(y); } void clear() { cnt = n; fill(begin(data), end(data), -1); } }; template struct Mod_Int { int x; Mod_Int() : x(0) {} Mod_Int(long long y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {} static int get_mod() { return mod; } Mod_Int &operator+=(const Mod_Int &p) { if ((x += p.x) >= mod) x -= mod; return *this; } Mod_Int &operator-=(const Mod_Int &p) { if ((x += mod - p.x) >= mod) x -= mod; return *this; } Mod_Int &operator*=(const Mod_Int &p) { x = (int)(1LL * x * p.x % mod); return *this; } Mod_Int &operator/=(const Mod_Int &p) { *this *= p.inverse(); return *this; } Mod_Int &operator++() { return *this += Mod_Int(1); } Mod_Int operator++(int) { Mod_Int tmp = *this; ++*this; return tmp; } Mod_Int &operator--() { return *this -= Mod_Int(1); } Mod_Int operator--(int) { Mod_Int tmp = *this; --*this; return tmp; } Mod_Int operator-() const { return Mod_Int(-x); } Mod_Int operator+(const Mod_Int &p) const { return Mod_Int(*this) += p; } Mod_Int operator-(const Mod_Int &p) const { return Mod_Int(*this) -= p; } Mod_Int operator*(const Mod_Int &p) const { return Mod_Int(*this) *= p; } Mod_Int operator/(const Mod_Int &p) const { return Mod_Int(*this) /= p; } bool operator==(const Mod_Int &p) const { return x == p.x; } bool operator!=(const Mod_Int &p) const { return x != p.x; } Mod_Int inverse() const { assert(*this != Mod_Int(0)); return pow(mod - 2); } Mod_Int pow(long long k) const { Mod_Int now = *this, ret = 1; for (; k > 0; k >>= 1, now *= now) { if (k & 1) ret *= now; } return ret; } friend ostream &operator<<(ostream &os, const Mod_Int &p) { return os << p.x; } friend istream &operator>>(istream &is, Mod_Int &p) { long long a; is >> a; p = Mod_Int(a); return is; } }; ll mpow(ll x, ll n, ll mod) { ll ans = 1; x %= mod; while (n != 0) { if (n & 1) ans = ans * x % mod; x = x * x % mod; n = n >> 1; } ans %= mod; return ans; } template T modinv(T a, const T &m) { T b = m, u = 1, v = 0; while (b > 0) { T t = a / b; swap(a -= t * b, b); swap(u -= t * v, v); } return u >= 0 ? u % m : (m - (-u) % m) % m; } ll divide_int(ll a, ll b) { if (b < 0) a = -a, b = -b; return (a >= 0 ? a / b : (a - b + 1) / b); } // const int MOD = 1000000007; const int MOD = 998244353; using mint = Mod_Int; // ----- library ------- template struct Binary_Indexed_Tree { vector bit; const int n; Binary_Indexed_Tree(const vector &v) : n((int)v.size()) { bit.resize(n + 1); copy(begin(v), end(v), begin(bit) + 1); for (int a = 2; a <= n; a <<= 1) { for (int b = a; b <= n; b += a) bit[b] += bit[b - a / 2]; } } Binary_Indexed_Tree(int n, const T &x) : Binary_Indexed_Tree(vector(n, x)) {} void add(int i, const T &x) { for (i++; i <= n; i += (i & -i)) bit[i] += x; } void change(int i, const T &x) { add(i, x - query(i, i + 1)); } T sum(int i) const { i = min(i, n); if (i <= 0) return 0; T ret = 0; for (; i > 0; i -= (i & -i)) ret += bit[i]; return ret; } T query(int l, int r) const { l = max(l, 0), r = min(r, n); if (l >= r) return 0; return sum(r) - sum(l); } T operator[](int i) const { return query(i, i + 1); } }; struct Runtime_Mod_Int1 { int x; Runtime_Mod_Int1() : x(0) {} Runtime_Mod_Int1(long long y) { x = y % get_mod(); if (x < 0) x += get_mod(); } static inline int &get_mod() { static int mod = INT_MAX; return mod; } static void set_mod(int mod) { get_mod() = mod; } Runtime_Mod_Int1 &operator+=(const Runtime_Mod_Int1 &p) { if ((x += p.x) >= get_mod()) x -= get_mod(); return *this; } Runtime_Mod_Int1 &operator-=(const Runtime_Mod_Int1 &p) { if ((x += get_mod() - p.x) >= get_mod()) x -= get_mod(); return *this; } Runtime_Mod_Int1 &operator*=(const Runtime_Mod_Int1 &p) { x = (int)(1LL * x * p.x % get_mod()); return *this; } Runtime_Mod_Int1 &operator/=(const Runtime_Mod_Int1 &p) { *this *= p.inverse(); return *this; } Runtime_Mod_Int1 &operator++() { return *this += Runtime_Mod_Int1(1); } Runtime_Mod_Int1 operator++(int) { Runtime_Mod_Int1 tmp = *this; ++*this; return tmp; } Runtime_Mod_Int1 &operator--() { return *this -= Runtime_Mod_Int1(1); } Runtime_Mod_Int1 operator--(int) { Runtime_Mod_Int1 tmp = *this; --*this; return tmp; } Runtime_Mod_Int1 operator-() const { return Runtime_Mod_Int1(-x); } Runtime_Mod_Int1 operator+(const Runtime_Mod_Int1 &p) const { return Runtime_Mod_Int1(*this) += p; } Runtime_Mod_Int1 operator-(const Runtime_Mod_Int1 &p) const { return Runtime_Mod_Int1(*this) -= p; } Runtime_Mod_Int1 operator*(const Runtime_Mod_Int1 &p) const { return Runtime_Mod_Int1(*this) *= p; } Runtime_Mod_Int1 operator/(const Runtime_Mod_Int1 &p) const { return Runtime_Mod_Int1(*this) /= p; } bool operator==(const Runtime_Mod_Int1 &p) const { return x == p.x; } bool operator!=(const Runtime_Mod_Int1 &p) const { return x != p.x; } Runtime_Mod_Int1 inverse() const { assert(*this != Runtime_Mod_Int1(0)); return pow(get_mod() - 2); } Runtime_Mod_Int1 pow(long long k) const { Runtime_Mod_Int1 now = *this, ret = 1; for (; k > 0; k >>= 1, now *= now) { if (k & 1) ret *= now; } return ret; } friend ostream &operator<<(ostream &os, const Runtime_Mod_Int1 &p) { return os << p.x; } friend istream &operator>>(istream &is, Runtime_Mod_Int1 &p) { long long a; is >> a; p = Runtime_Mod_Int1(a); return is; } }; struct Runtime_Mod_Int2 { int x; Runtime_Mod_Int2() : x(0) {} Runtime_Mod_Int2(long long y) { x = y % get_mod(); if (x < 0) x += get_mod(); } static inline int &get_mod() { static int mod = INT_MAX; return mod; } static void set_mod(int mod) { get_mod() = mod; } Runtime_Mod_Int2 &operator+=(const Runtime_Mod_Int2 &p) { if ((x += p.x) >= get_mod()) x -= get_mod(); return *this; } Runtime_Mod_Int2 &operator-=(const Runtime_Mod_Int2 &p) { if ((x += get_mod() - p.x) >= get_mod()) x -= get_mod(); return *this; } Runtime_Mod_Int2 &operator*=(const Runtime_Mod_Int2 &p) { x = (int)(1LL * x * p.x % get_mod()); return *this; } Runtime_Mod_Int2 &operator/=(const Runtime_Mod_Int2 &p) { *this *= p.inverse(); return *this; } Runtime_Mod_Int2 &operator++() { return *this += Runtime_Mod_Int2(1); } Runtime_Mod_Int2 operator++(int) { Runtime_Mod_Int2 tmp = *this; ++*this; return tmp; } Runtime_Mod_Int2 &operator--() { return *this -= Runtime_Mod_Int2(1); } Runtime_Mod_Int2 operator--(int) { Runtime_Mod_Int2 tmp = *this; --*this; return tmp; } Runtime_Mod_Int2 operator-() const { return Runtime_Mod_Int2(-x); } Runtime_Mod_Int2 operator+(const Runtime_Mod_Int2 &p) const { return Runtime_Mod_Int2(*this) += p; } Runtime_Mod_Int2 operator-(const Runtime_Mod_Int2 &p) const { return Runtime_Mod_Int2(*this) -= p; } Runtime_Mod_Int2 operator*(const Runtime_Mod_Int2 &p) const { return Runtime_Mod_Int2(*this) *= p; } Runtime_Mod_Int2 operator/(const Runtime_Mod_Int2 &p) const { return Runtime_Mod_Int2(*this) /= p; } bool operator==(const Runtime_Mod_Int2 &p) const { return x == p.x; } bool operator!=(const Runtime_Mod_Int2 &p) const { return x != p.x; } Runtime_Mod_Int2 inverse() const { assert(*this != Runtime_Mod_Int2(0)); return pow(get_mod() - 2); } Runtime_Mod_Int2 pow(long long k) const { Runtime_Mod_Int2 now = *this, ret = 1; for (; k > 0; k >>= 1, now *= now) { if (k & 1) ret *= now; } return ret; } friend ostream &operator<<(ostream &os, const Runtime_Mod_Int2 &p) { return os << p.x; } friend istream &operator>>(istream &is, Runtime_Mod_Int2 &p) { long long a; is >> a; p = Runtime_Mod_Int2(a); return is; } }; // ----- library ------- int main() { ios::sync_with_stdio(false); std::cin.tie(nullptr); cout << fixed << setprecision(15); int n, b, q; cin >> n >> b >> q; using modb = Runtime_Mod_Int1; modb::set_mod(b); vector c(5), d(5); rep(k, 5) cin >> c[k] >> d[k]; vector a(n); a[0] = c[0]; rep(k, n - 1) a[k + 1] = a[k] * d[0]; using modn = Runtime_Mod_Int2; modn::set_mod(n); vector i(q), j(q); vector x(q), y(q); i[0] = c[1]; j[0] = c[2]; x[0] = c[3]; y[0] = c[4]; rep(k, q - 1) { i[k + 1] = i[k] * d[1]; j[k + 1] = j[k] * d[2]; x[k + 1] = x[k] * d[3]; y[k + 1] = y[k] * d[4]; } Binary_Indexed_Tree bit(a); vector p(n); rep2(k, 1, n) p[k] = k - (k & (-k)); rep(k, q) { bit.add(i[k].x, x[k] - a[k]); a[i[k].x] = x[k]; modb ans = 0, po = 1; while (1) { if (j[k] == 0) { ans += a[0] * po; break; } ans += bit.query(p[j[k].x] + 1, j[k].x + 1) * po; po *= y[k]; j[k] = p[j[k].x]; } cout << ans << '\n'; } }