#include #include #include #include #include // using namespace std; // using namespace atcoder; // using mint = modint998244353; template struct mat22 { using mat_t = std::array; mat_t a; mat22() : a{} {} mat22(const mat_t &a_) : a(a_) {} // mat22(const Vec &v) : h(v.size()), w(1) // { // for (auto x : v) { // a.push_back({x}); // } // } static mat22 unit() { mat22 u; u[0] = 1; u[3] = 1; return u; } T &operator[](int i) { return a[i]; } const T &operator[](int i) const { return a[i]; } // Vec as_vec() const // { // assert(w == 1); // Vec ans; // for (int i = 0; i < h; i++) { // ans.push_back(a[i][0]); // } // return ans; // } mat22 operator*(const mat22 &b) const { mat22 ans{}; for (int i = 0; i < 2; i++) { for (int j = 0; j < 2; j++) { for (int k = 0; k < 2; k++) { // ans.a[i][k] += a[i][j] * b.a[j][k]; ans[i * 2 + j] += a[i * 2 + k] * b[k * 2 + j]; } } } return ans; } // void print() const // { // cout << "[\n"; // for (auto &ai : a) { // cout << " ( "; // for (auto &b : ai) { // cout << b.val() << " "; // } // cout << ")" << endl; // } // cout << "]" << endl; // } mat22 pow(long long n) const { if (!n) return mat22::unit(); if (n == 1) return *this; mat22 h = pow(n >> 1); h = h * h; if (n & 1) h = h * (*this); return h; // mat22 x = *this, r = mat22(h, h).unit(); // while (n) { // if (n & 1) r = r * x; // x = x * x; // n >>= 1; // } // return r; } static mat22 read() { mat22 m; for (auto &e : m.a) { long long x; std::cin >> x; e = x; } return m; } }; template struct Binomial { std::vector fact, invfact; Binomial(int nn) : fact(nn, 1), invfact(nn, 1) { for (int i = 0; i < nn - 1; i++) fact[i + 1] = fact[i] * (i + 1); invfact[nn - 1] = fact[nn - 1].inv(); for (int i = nn - 2; i >= 0; i--) invfact[i] = invfact[i + 1] * (i + 1); } Mint operator()(int x, int y) const { if (x < 0 || y < 0 || x - y < 0) return 0; return fact[x] * invfact[y] * invfact[x - y]; } }; using mint = atcoder::modint; mat22 e() { return mat22::unit(); } mat22 op(mat22 a, mat22 b) { return a * b; } int main() { using namespace std; using lint = long long; lint k, n; cin >> k >> n; mint::set_mod(k); vector> a0(n); for (auto& ai: a0) { ai = mat22::read(); } atcoder::segtree, op, e> seg(a0); int q; cin >> q; while (q --> 0) { int i, l, r; cin >> i >> l >> r; auto y = mat22::read(); i--; l--; seg.set(i, y); auto z = seg.prod(l, r); cout << z[0].val() << " " << z[1].val() << "\n"; cout << z[2].val() << " " << z[3].val() << "\n"; } }