// #define _GLIBCXX_DEBUG #include // clang-format off std::ostream&operator<<(std::ostream&os,std::int8_t x){return os<<(int)x;} std::ostream&operator<<(std::ostream&os,std::uint8_t x){return os<<(int)x;} std::ostream&operator<<(std::ostream&os,const __int128_t &u){if(!u)os<<"0";__int128_t tmp=u<0?(os<<"-",-u):u;std::string s;while(tmp)s+='0'+(tmp%10),tmp/=10;return std::reverse(s.begin(),s.end()),os< template constexpr inline Int mod_inv(Int a, Int mod) { static_assert(std::is_signed_v); Int x= 1, y= 0, b= mod; for (Int q= 0, z= 0; b;) z= x, x= y, y= z - y * (q= a / b), z= a, a= b, b= z - b * q; return assert(a == 1), x < 0 ? mod - (-x) % mod : x % mod; } namespace math_internal { using namespace std; using u8= unsigned char; using u32= unsigned; using i64= long long; using u64= unsigned long long; using u128= __uint128_t; #define CE constexpr #define IL inline #define NORM \ if (n >= mod) n-= mod; \ return n #define PLUS(U, M) \ CE IL U plus(U l, U r) const { return l+= r, l < (M) ? l : l - (M); } #define DIFF(U, C, M) \ CE IL U diff(U l, U r) const { return l-= r, l >> C ? l + (M) : l; } #define SGN(U) \ static CE IL U set(U n) { return n; } \ static CE IL U get(U n) { return n; } \ static CE IL U norm(U n) { return n; } template struct MP_Mo { u_t mod; CE MP_Mo(): mod(0), iv(0), r2(0) {} CE MP_Mo(u_t m): mod(m), iv(inv(m)), r2(-du_t(mod) % mod) {} CE IL u_t mul(u_t l, u_t r) const { return reduce(du_t(l) * r); } PLUS(u_t, mod << 1) DIFF(u_t, A, mod << 1) CE IL u_t set(u_t n) const { return mul(n, r2); } CE IL u_t get(u_t n) const { n= reduce(n); NORM; } CE IL u_t norm(u_t n) const { NORM; } private: u_t iv, r2; static CE u_t inv(u_t n, int e= 6, u_t x= 1) { return e ? inv(n, e - 1, x * (2 - x * n)) : x; } CE IL u_t reduce(const du_t &w) const { return u_t(w >> B) + mod - ((du_t(u_t(w) * iv) * mod) >> B); } }; struct MP_Na { u32 mod; CE MP_Na(): mod(0){}; CE MP_Na(u32 m): mod(m) {} CE IL u32 mul(u32 l, u32 r) const { return u64(l) * r % mod; } PLUS(u32, mod) DIFF(u32, 31, mod) SGN(u32) }; struct MP_Br { // mod < 2^31 u32 mod; CE MP_Br(): mod(0), s(0), x(0) {} CE MP_Br(u32 m): mod(m), s(95 - __builtin_clz(m - 1)), x(((u128(1) << s) + m - 1) / m) {} CE IL u32 mul(u32 l, u32 r) const { return rem(u64(l) * r); } PLUS(u32, mod) DIFF(u32, 31, mod) SGN(u32) private: u8 s; u64 x; CE IL u64 quo(u64 n) const { return (u128(x) * n) >> s; } CE IL u32 rem(u64 n) const { return n - quo(n) * mod; } }; struct MP_Br2 { // 2^20 < mod <= 2^41 u64 mod; CE MP_Br2(): mod(0), x(0) {} CE MP_Br2(u64 m): mod(m), x((u128(1) << 84) / m) {} CE IL u64 mul(u64 l, u64 r) const { return rem(u128(l) * r); } PLUS(u64, mod << 1) DIFF(u64, 63, mod << 1) static CE IL u64 set(u64 n) { return n; } CE IL u64 get(u64 n) const { NORM; } CE IL u64 norm(u64 n) const { NORM; } private: u64 x; CE IL u128 quo(const u128 &n) const { return (n * x) >> 84; } CE IL u64 rem(const u128 &n) const { return n - quo(n) * mod; } }; struct MP_D2B1 { u8 s; u64 mod, d, v; CE MP_D2B1(): s(0), mod(0), d(0), v(0) {} CE MP_D2B1(u64 m): s(__builtin_clzll(m)), mod(m), d(m << s), v(u128(-1) / d) {} CE IL u64 mul(u64 l, u64 r) const { return rem((u128(l) * r) << s) >> s; } PLUS(u64, mod) DIFF(u64, 63, mod) SGN(u64) private: CE IL u64 rem(const u128 &u) const { u128 q= (u >> 64) * v + u; u64 r= u64(u) - (q >> 64) * d - d; if (r > u64(q)) r+= d; if (r >= d) r-= d; return r; } }; template CE u_t pow(u_t x, u64 k, const MP &md) { for (u_t ret= md.set(1);; x= md.mul(x, x)) if (k & 1 ? ret= md.mul(ret, x) : 0; !(k>>= 1)) return ret; } #undef NORM #undef PLUS #undef DIFF #undef SGN #undef CE } namespace math_internal { struct m_b {}; struct s_b: m_b {}; } template constexpr bool is_modint_v= std::is_base_of_v; template constexpr bool is_staticmodint_v= std::is_base_of_v; namespace math_internal { #define CE constexpr template struct SB: s_b { protected: static CE MP md= MP(MOD); }; template struct MInt: public B { using Uint= U; static CE inline auto mod() { return B::md.mod; } CE MInt(): x(0) {} template && !is_same_v>> CE MInt(T v): x(B::md.set(v.val() % B::md.mod)) {} CE MInt(__int128_t n): x(B::md.set((n < 0 ? ((n= (-n) % B::md.mod) ? B::md.mod - n : n) : n % B::md.mod))) {} CE MInt operator-() const { return MInt() - *this; } #define FUNC(name, op) \ CE MInt name const { \ MInt ret; \ return ret.x= op, ret; \ } FUNC(operator+(const MInt & r), B::md.plus(x, r.x)) FUNC(operator-(const MInt & r), B::md.diff(x, r.x)) FUNC(operator*(const MInt & r), B::md.mul(x, r.x)) FUNC(pow(u64 k), math_internal::pow(x, k, B::md)) #undef FUNC CE MInt operator/(const MInt& r) const { return *this * r.inv(); } CE MInt& operator+=(const MInt& r) { return *this= *this + r; } CE MInt& operator-=(const MInt& r) { return *this= *this - r; } CE MInt& operator*=(const MInt& r) { return *this= *this * r; } CE MInt& operator/=(const MInt& r) { return *this= *this / r; } CE bool operator==(const MInt& r) const { return B::md.norm(x) == B::md.norm(r.x); } CE bool operator!=(const MInt& r) const { return !(*this == r); } CE bool operator<(const MInt& r) const { return B::md.norm(x) < B::md.norm(r.x); } CE inline MInt inv() const { return mod_inv(val(), B::md.mod); } CE inline Uint val() const { return B::md.get(x); } friend ostream& operator<<(ostream& os, const MInt& r) { return os << r.val(); } friend istream& operator>>(istream& is, MInt& r) { i64 v; return is >> v, r= MInt(v), is; } private: Uint x; }; template using ModInt= conditional_t < (MOD < (1 << 30)) & MOD, MInt, MOD>>, conditional_t < (MOD < (1ull << 62)) & MOD, MInt, MOD>>, conditional_t>, conditional_t>, conditional_t>, MInt>>>>>>; #undef CE } using math_internal::ModInt; namespace _la_internal { using namespace std; template struct Vector { valarray dat; Vector()= default; Vector(size_t n): dat(n) {} Vector(size_t n, const R &v): dat(v, n) {} Vector(const initializer_list &v): dat(v) {} R &operator[](int i) { return dat[i]; } const R &operator[](int i) const { return dat[i]; } bool operator==(const Vector &r) const { if (dat.size() != r.dat.size()) return false; for (int i= dat.size(); i--;) if (dat[i] != r.dat[i]) return false; return true; } bool operator!=(const Vector &r) const { return !(*this == r); } explicit operator bool() const { return dat.size(); } Vector operator-() const { return Vector(dat.size())-= *this; } Vector &operator+=(const Vector &r) { return dat+= r.dat, *this; } Vector &operator-=(const Vector &r) { return dat-= r.dat, *this; } Vector &operator*=(const R &r) { return dat*= r, *this; } Vector operator+(const Vector &r) const { return Vector(*this)+= r; } Vector operator-(const Vector &r) const { return Vector(*this)-= r; } Vector operator*(const R &r) const { return Vector(*this)*= r; } size_t size() const { return dat.size(); } friend R dot(const Vector &a, const Vector &b) { return assert(a.size() == b.size()), (a.dat * b.dat).sum(); } }; using u128= __uint128_t; using u64= uint64_t; using u8= uint8_t; class Ref { u128 *ref; u8 i; public: Ref(u128 *ref, u8 i): ref(ref), i(i) {} Ref &operator=(const Ref &r) { return *this= bool(r); } Ref &operator=(bool b) { return *ref&= ~(u128(1) << i), *ref|= u128(b) << i, *this; } Ref &operator|=(bool b) { return *ref|= u128(b) << i, *this; } Ref &operator&=(bool b) { return *ref&= ~(u128(!b) << i), *this; } Ref &operator^=(bool b) { return *ref^= u128(b) << i, *this; } operator bool() const { return (*ref >> i) & 1; } }; template <> class Vector { size_t n; public: valarray dat; Vector(): n(0) {} Vector(size_t n): n(n), dat((n + 127) >> 7) {} Vector(size_t n, bool b): n(n), dat(-u128(b), (n + 127) >> 7) { if (int k= n & 127; k) dat[dat.size() - 1]&= (u128(1) << k) - 1; } Vector(const initializer_list &v): n(v.size()), dat((n + 127) >> 7) { int i= 0; for (bool b: v) dat[i >> 7]|= u128(b) << (i & 127), ++i; } Ref operator[](int i) { return {begin(dat) + (i >> 7), u8(i & 127)}; } bool operator[](int i) const { return (dat[i >> 7] >> (i & 127)) & 1; } bool operator==(const Vector &r) const { if (dat.size() != r.dat.size()) return false; for (int i= dat.size(); i--;) if (dat[i] != r.dat[i]) return false; return true; } bool operator!=(const Vector &r) const { return !(*this == r); } explicit operator bool() const { return n; } Vector operator-() const { return Vector(*this); } Vector &operator+=(const Vector &r) { return dat^= r.dat, *this; } Vector &operator-=(const Vector &r) { return dat^= r.dat, *this; } Vector &operator*=(bool b) { return dat*= b, *this; } Vector operator+(const Vector &r) const { return Vector(*this)+= r; } Vector operator-(const Vector &r) const { return Vector(*this)-= r; } Vector operator*(bool b) const { return Vector(*this)*= b; } size_t size() const { return n; } friend bool dot(const Vector &a, const Vector &b) { assert(a.size() == b.size()); u128 v= 0; for (int i= a.dat.size(); i--;) v^= a.dat[i] & b.dat[i]; return __builtin_parityll(v >> 64) ^ __builtin_parityll(u64(v)); } }; template Vector operator*(const R &r, const Vector &v) { return v * r; } template ostream &operator<<(ostream &os, const Vector &v) { os << '['; for (int _= 0, __= v.size(); _ < __; ++_) os << (_ ? ", " : "") << v[_]; return os << ']'; } } using _la_internal::Vector; namespace _la_internal { template struct Mat { Mat(): W(0) {} Mat(size_t h, size_t w): W(w), dat(h * w) {} Mat(size_t h, size_t w, R v): W(w), dat(v, h * w) {} Mat(initializer_list> v): W(v.size() ? v.begin()->size() : 0), dat(v.size() * W) { auto it= begin(dat); for (const auto &r: v) { assert(r.size() == W); for (R x: r) *it++= x; } } size_t width() const { return W; } size_t height() const { return W ? dat.size() / W : 0; } auto operator[](int i) { return next(begin(dat), i * W); } auto operator[](int i) const { return next(begin(dat), i * W); } protected: size_t W; valarray dat; void add(const Mat &r) { assert(dat.size() == r.dat.size()), assert(W == r.W), dat+= r.dat; } D mul(const Mat &r) const { const size_t h= height(), w= r.W, l= W; assert(l == r.height()); D ret(h, w); auto a= begin(dat); auto c= begin(ret.dat); for (int i= h; i--; advance(c, w)) { auto b= begin(r.dat); for (int k= l; k--; ++a) { auto d= c; auto v= *a; for (int j= w; j--; ++b, ++d) *d+= v * *b; } } return ret; } Vector mul(const Vector &r) const { assert(W == r.size()); const size_t h= height(); Vector ret(h); auto a= begin(dat); for (size_t i= 0; i < h; ++i) for (size_t k= 0; k < W; ++k, ++a) ret[i]+= *a * r[k]; return ret; } }; template struct Mat { struct Array { u128 *bg; Array(u128 *it): bg(it) {} Ref operator[](int i) { return Ref{bg + (i >> 7), u8(i & 127)}; } bool operator[](int i) const { return (bg[i >> 7] >> (i & 127)) & 1; } }; struct ConstArray { const u128 *bg; ConstArray(const u128 *it): bg(it) {} bool operator[](int i) const { return (bg[i >> 7] >> (i & 127)) & 1; } }; Mat(): H(0), W(0), m(0) {} Mat(size_t h, size_t w): H(h), W(w), m((w + 127) >> 7), dat(h * m) {} Mat(size_t h, size_t w, bool b): H(h), W(w), m((w + 127) >> 7), dat(-u128(b), h * m) { if (size_t i= h, k= w & 127; k) for (u128 s= (u128(1) << k) - 1; i--;) dat[i * m]&= s; } Mat(const initializer_list> &v): H(v.size()), W(H ? v.begin()->size() : 0), m((W + 127) >> 7), dat(H * m) { auto it= begin(dat); for (const auto &r: v) { assert(r.size() == W); int i= 0; for (bool b: r) it[i >> 7]|= u128(b) << (i & 127), ++i; advance(it, m); } } size_t width() const { return W; } size_t height() const { return H; } Array operator[](int i) { return {next(begin(dat), i * m)}; } ConstArray operator[](int i) const { return {next(begin(dat), i * m)}; } ConstArray get(int i) const { return {next(begin(dat), i * m)}; } protected: size_t H, W, m; valarray dat; void add(const Mat &r) { assert(H == r.H), assert(W == r.W), dat^= r.dat; } D mul(const Mat &r) const { assert(W == r.H); D ret(H, r.W); u128 *c= begin(ret.dat); for (size_t i= 0; i < H; ++i, advance(c, r.m)) { ConstArray a= this->operator[](i); const u128 *b= begin(r.dat); for (size_t k= 0; k < W; ++k, advance(b, r.m)) if (a[k]) for (size_t j= 0; j < r.m; ++j) c[j]^= b[j]; } return ret; } Vector mul(const Vector &r) const { assert(W == r.size()); Vector ret(H); auto a= begin(dat); for (size_t i= 0; i < H; ++i) { u128 v= 0; for (size_t j= 0; j < m; ++j, ++a) v^= *a & r.dat[j]; ret[i]= __builtin_parityll(v >> 64) ^ __builtin_parityll(u64(v)); } return ret; } }; template struct Matrix: public Mat> { using Mat>::Mat; explicit operator bool() const { return this->W; } static Matrix identity_matrix(int n) { Matrix ret(n, n); for (; n--;) ret[n][n]= R(true); return ret; } Matrix submatrix(const vector &rows, const vector &cols) const { Matrix ret(rows.size(), cols.size()); for (int i= rows.size(); i--;) for (int j= cols.size(); j--;) ret[i][j]= (*this)[rows[i]][cols[j]]; return ret; } Matrix submatrix_rm(vector rows, vector cols) const { sort(begin(rows), end(rows)), sort(begin(cols), end(cols)), rows.erase(unique(begin(rows), end(rows)), end(rows)), cols.erase(unique(begin(cols), end(cols)), end(cols)); const int H= this->height(), W= this->width(), n= rows.size(), m= cols.size(); vector rs(H - n), cs(W - m); for (int i= 0, j= 0, k= 0; i < H; ++i) if (j < n && rows[j] == i) ++j; else rs[k++]= i; for (int i= 0, j= 0, k= 0; i < W; ++i) if (j < m && cols[j] == i) ++j; else cs[k++]= i; return submatrix(rs, cs); } bool operator==(const Matrix &r) const { if (this->width() != r.width() || this->height() != r.height()) return false; for (int i= this->dat.size(); i--;) if (this->dat[i] != r.dat[i]) return false; return true; } bool operator!=(const Matrix &r) const { return !(*this == r); } Matrix &operator*=(const Matrix &r) { return *this= this->mul(r); } Matrix operator*(const Matrix &r) const { return this->mul(r); } Matrix &operator*=(R r) { return this->dat*= r, *this; } template Matrix operator*(T r) const { static_assert(is_convertible_v); return Matrix(*this)*= r; } Matrix &operator+=(const Matrix &r) { return this->add(r), *this; } Matrix operator+(const Matrix &r) const { return Matrix(*this)+= r; } Vector operator*(const Vector &r) const { return this->mul(r); } Vector operator()(const Vector &r) const { return this->mul(r); } Matrix pow(uint64_t k) const { size_t W= this->width(); assert(W == this->height()); for (Matrix ret= identity_matrix(W), b= *this;; b*= b) if (k & 1 ? ret*= b, !(k>>= 1) : !(k>>= 1)) return ret; } }; template Matrix operator*(const T &r, const Matrix &m) { return m * r; } template ostream &operator<<(ostream &os, const Matrix &m) { os << "\n["; for (int i= 0, h= m.height(); i < h; os << ']', ++i) { if (i) os << "\n "; os << '['; for (int j= 0, w= m.width(); j < w; ++j) os << (j ? ", " : "") << m[i][j]; } return os << ']'; } template static bool is_zero(K x) { if constexpr (is_floating_point_v) return abs(x) < 1e-8; else return x == K(); } } using _la_internal::Matrix; template struct SegmentTree { using T= typename M::T; SegmentTree() {} SegmentTree(int n_): n(n_), dat(n << 1, M::ti()) {} SegmentTree(int n_, T v): n(n_), dat(n << 1, M::ti()) { for (int i= n; i--;) dat[i + n]= v; rebuild(); } SegmentTree(const std::vector &v): n(v.size()), dat(n << 1, M::ti()) { for (int i= n; i--;) dat[i + n]= v[i]; rebuild(); } void set(int k, T x) { for (dat[k+= n]= x; k>>= 1;) dat[k]= M::op(dat[(k << 1) | 0], dat[(k << 1) | 1]); } void unsafe_set(int k, T x) { dat[k + n]= x; } void rebuild() { for (int i= n; --i;) dat[i]= M::op(dat[i << 1 | 0], dat[i << 1 | 1]); } void clear() { fill(dat.begin(), dat.end(), M::ti()); } inline T fold(int l, int r) const { //[l,r) T vl= M::ti(), vr= M::ti(); for (int a= l + n, b= r + n; a < b; a>>= 1, b>>= 1) { if (a & 1) vl= M::op(vl, dat[a++]); if (b & 1) vr= M::op(dat[--b], vr); } return M::op(vl, vr); } T operator[](const int &k) const { return dat[k + n]; } template static inline T calc_op(const T &v, const T &d) { if constexpr (last) return M::op(d, v); else return M::op(v, d); } // Case 0. find i s.t check(fold(k,i)) == False, check(fold(k,i+1)) == True // Case 1. find i s.t check(fold(i+1,b)) == False, check(fold(i,b)) == True // return -1 if not found template int find(const C &check, int k) const { assert(!check(M::ti())); std::vector id[2]; int a= n + (k & -(!last)), b= n + n + ((k - n) & -(last)); for (; a < b; a>>= 1, b>>= 1) { if (a & 1) id[0].push_back(a++); if (b & 1) id[1].push_back(--b); } id[last].insert(id[last].end(), id[!last].rbegin(), id[!last].rend()); T val= M::ti(); for (int i: id[last]) { if (T tmp= calc_op(val, dat[i]); check(tmp)) { while (i < n) if (tmp= calc_op(val, dat[i= i << 1 | last]); !check(tmp)) val= tmp, i-= last * 2 - 1; return i - n + last; } else val= tmp; } return -1; } private: const int n; std::vector dat; }; using namespace std; using Mint= ModInt; using Mat= Matrix; struct Mono { using T= array; static T op(const T &a, const T &b) { return {b[0] * a[0], a[2] * b[1] * a[0] + a[1], a[2] * b[2]}; } static T ti() { return {Mat::identity_matrix(3), Mat(2, 3), Mat::identity_matrix(2)}; } }; signed main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; SegmentTree seg(N + 1); for (int i= 0; i <= N; ++i) { Mint s= 6 * i; Mat S= {{s, s + 1, s + 2}, {s + 3, s + 4, s + 5}}; seg.unsafe_set(i, {Mat::identity_matrix(3), S, Mat::identity_matrix(2)}); } seg.rebuild(); Vector a(3), b(2); cin >> a[0] >> a[1] >> a[2] >> b[0] >> b[1]; int q; cin >> q; while (q--) { string s; int i; cin >> s >> i; if (s == "a") { Mat A(3, 3); cin >> A[0][0] >> A[0][1] >> A[0][2] >> A[1][0] >> A[1][1] >> A[1][2] >> A[2][0] >> A[2][1] >> A[2][2]; auto [X, Y, Z]= seg[i]; seg.set(i, {A, Y, Z}); } else if (s == "b") { Mat B(2, 2); cin >> B[0][0] >> B[0][1] >> B[1][0] >> B[1][1]; auto [X, Y, Z]= seg[i]; seg.set(i, {X, Y, B}); } else if (s == "ga") { auto ans= seg.fold(0, i)[0] * a; cout << ans[0] << " " << ans[1] << " " << ans[2] << '\n'; } else { auto [X, Y, Z]= seg.fold(i + 1, N + 1); auto ans= Z * b + Y * seg.fold(0, i + 1)[0] * a; cout << ans[0] << " " << ans[1] << '\n'; } } return 0; }