#include using namespace std; #define _MACRO(_1, _2, _3, NAME, ...) NAME #define _repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++) #define _rep(i,n) _repl(i,0,n) #define rep(...) _MACRO(__VA_ARGS__, _repl, _rep)(__VA_ARGS__) #define mp make_pair #define pb push_back #define all(x) begin(x),end(x) #define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x)) #define fi first #define se second #define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__) void _dbg(string){cerr< void _dbg(string s,H h,T... t){int l=s.find(',');cerr< ostream& operator<<(ostream &o, const pair &p){o<<"("< ostream& operator<<(ostream &o, const vector &v){o<<"[";for(T t:v){o< class ModInt { int x; public: ModInt() : x(0) {} ModInt(const ModInt &y): x(y.x) {} ModInt(int64_t y){ x = y % mod; if(x < 0) x += mod; } ModInt &operator += (const ModInt &p){ x += p.x; if(x >= mod) x -= mod; return *this; } ModInt &operator -= (const ModInt &p){ x -= p.x; if(x < 0) x += mod; return *this; } ModInt &operator *= (const ModInt &p){ x = (int) (1LL * x * p.x % mod); return *this; } ModInt &operator /= (const ModInt &p){ *this *= p.inverse(); return *this; } ModInt operator -() const { return ModInt(-x); } ModInt operator + (const ModInt &p) const { return ModInt(*this) += p; } ModInt operator - (const ModInt &p) const { return ModInt(*this) -= p; } ModInt operator * (const ModInt &p) const { return ModInt(*this) *= p; } ModInt operator / (const ModInt &p) const { return ModInt(*this) /= p; } bool operator == (const ModInt &p) const { return x == p.x; } bool operator != (const ModInt &p) const { return x != p.x; } ModInt operator = (const int64_t y) { return *this = ModInt(y); } ModInt inverse() const { int a = x, b = mod, u = 1, v = 0, t; while(b > 0){ t = a/b; a -= t*b; swap(a, b); u -= t*v; swap(u, v); } return ModInt(u); } ModInt pow(int64_t y) const { if(x==0) return ModInt(0); int64_t r = 1, t = x; while(y > 0){ if(y&1) r = r*t%mod; t = t*t%mod; y >>= 1; } return ModInt(r); } friend ostream &operator << (ostream &os, const ModInt &p) { return os<> (istream &is, ModInt &a) { int64_t x; is>>x; a = ModInt(x); return is; } }; using Int = ModInt<>; struct mat { Int a,b,c,d; mat() : a(1), b(0), c(0), d(1) {} mat(Int a0, Int a1, Int a2, Int a3) : a(a0), b(a1), c(a2), d(a3) {} mat &operator *= (const mat &p){ Int n0 = a*p.a + b*p.c; Int n1 = a*p.b + b*p.d; Int n2 = c*p.a + d*p.c; Int n3 = c*p.b + d*p.d; a = n0; b = n1; c = n2; d = n3; return *this; } mat operator * (const mat &p) const { return mat(*this) *= p; } mat inverse() const { Int id = (a*d - b*c).inverse(); return mat(id*d, -id*b, -id*c, id*a); } friend ostream &operator << (ostream &os, const mat &p) { os << p.a << " " << p.b << " " << p.c << " " << p.d; return os; } }; template class SegTree { public: int n; T e; T (*op)(T, T); vector data; SegTree(int m, T _e, T (*_op)(T, T)) : e(_e), op(_op){ n=1; while(n &v, T _e, T (*_op)(T, T)) : e(_e), op(_op){ // not well verified yet n=1; while(n0; i--) data[i] = op(data[i*2], data[i*2+1]); } T query(int l, int r){ T vl = e, vr = e; for(l+=n, r+=n; l0){ k = k/2; data[k] = op(data[k*2], data[k*2+1]); } } inline T operator[](int idx){ return data[idx+n]; } }; vector> tree[100005]; // to,id int bg[100005]; int ed[100005]; int id_in[100005]; int id_out[100005]; int tc = 0; void build(int v, int from){ bg[v] = tc++; for(auto to : tree[v]) if(to.fi != from){ id_in[to.se] = tc; build(to.fi, v); id_out[to.se] = tc-1; } ed[v] = tc++; } int main(){ int n; cin>>n; rep(i,n-1){ int a,b; cin>>a>>b; tree[a].pb({b,i}); tree[b].pb({a,i}); } build(0, -1); SegTree st(2*n, mat(), [](mat l, mat r){return l*r;}); int q; cin>>q; rep(_,q){ string s; cin>>s; if(s[0]=='g'){ int l,r; cin>>l>>r; cout << st.query(bg[l]+1, bg[r]+1) << "\n"; } else { int p,a,b,c,d; cin>>p>>a>>b>>c>>d; st.update(id_in[p], mat(a,b,c,d)); st.update(id_out[p], mat(a,b,c,d).inverse()); } } return 0; }