#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
const ll inf = 1e18;
mt19937 rnd(234);
const ll mod = 998244353;
template<int x, int y>
using mat = array<array<int, y>, x>;
template<int x, int y, int z>
mat<x, z> mul(const mat<x, y>& a, const mat <y, z>& b) {
mat<x, z> c;
for (int i = 0; i < x; i += 1) {
for (int k = 0; k < z; k += 1) {
c[i][k] = 0;
for (int j = 0; j < y; j += 1) {
c[i][k] = (c[i][k] + ((ll)a[i][j]) * b[j][k]) % mod;
}
}
}
return c;
}
mat<3, 3> flex() {
return { array<int, 3>{1, 0, 0},
array<int, 3>{0, 1, 0},
array<int, 3>{0, 0, 1} };
}
inline int neg(int a) {
if (a == 0) {
return 0;
}
return mod - a;
}
mat<3, 3> get_matrix(const mat<1, 3>& a, bool chipi_chipi_chapa_chapa = false) {
int x = a[0][0], y = a[0][1], z = a[0][2];
if (!chipi_chipi_chapa_chapa) {
return { array<int, 3>{0, neg(z), y},
array<int, 3>{z, 0, neg(x)},
array<int, 3>{neg(y), x, 0} };
}
return { array<int, 3>{0, z, neg(y)},
array<int, 3>{neg(z), 0, x},
array<int, 3>{y, neg(x), 0} };
}
mat<1, 3> prod(const mat<1, 3>& a, const mat<1, 3>& b) {
return mul<1, 3, 3>(a, get_matrix(b));
}
struct SGT {
struct node {
mat<3, 3> x;
mat<3, 3> sum;
int l = -1;
int r = -1;
int sz = 0;
node() {}
node(const mat<3, 3>& _x) {
x = _x;
sum = x;
sz = 1;
}
};
int n;
vector<node> t;
int rt;
void upd(int v) {
int l = t[v].l;
int r = t[v].r;
t[v].sum = flex();
t[v].sz = 1;
if (r != -1) {
t[v].sz += t[r].sz;
t[v].sum = mul<3, 3, 3>(t[v].sum, t[r].sum);
}
t[v].sum = mul<3, 3, 3>(t[v].sum, t[v].x);
if (l != -1) {
t[v].sz += t[l].sz;
t[v].sum = mul<3, 3, 3>(t[v].sum, t[l].sum);
}
}
int build(int tl, int tr, const vector<mat<1, 3>>& a, const vector<int>& p) {
if (tl > tr) {
return -1;
}
int sm = 0;
for (int i = tl; i <= tr; i += 1) {
sm += p[i];
}
int tm = -1;
int x = 0;
for (int i = tl; i <= tr; i += 1) {
x += p[i];
if (2 * x > sm) {
tm = i;
break;
}
}
assert(tm != -1);
int v = (int)t.size();
t.push_back(node(get_matrix(a[tm])));
t[v].l = build(tl, tm - 1, a, p);
t[v].r = build(tm + 1, tr, a, p);
upd(v);
return v;
}
void build(const vector<mat<1, 3>>& a, const vector<int>& p) {
n = (int)a.size();
t.clear();
rt = build(0, n - 1, a, p);
}
void chng(int v, int i, const mat<1, 3>& x) {
int l = t[v].l;
int lsz = (l == -1) ? 0 : t[l].sz;
if (i < lsz) {
chng(l, i, x);
upd(v);
return;
}
if (i == lsz) {
t[v].x = get_matrix(x);
upd(v);
return;
}
int r = t[v].r;
chng(r, i - lsz - 1, x);
upd(v);
}
void chng(int i, const mat<1, 3>& x) {
chng(rt, i, x);
}
mat<3, 3> get() {
if (rt == -1) {
return flex();
}
return t[rt].sum;
}
};
struct query {
int v;
int x, y, z;
};
int n, q;
vector<vector<int>> g;
vector<mat<1, 3>> val;
int c;
vector<query> biba;
vector<int> sz;
bool do_neg;
vector<int> clr;
void build_dfs(int v) {
sz[v] = 1;
for (auto to : g[v]) {
build_dfs(to);
sz[v] += sz[to];
}
if ((int)g[v].size() == 0) {
return;
}
assert((int)g[v].size() == 2);
int& l = g[v][0];
int& r = g[v][1];
if (sz[l] < sz[r]) {
swap(l, r);
do_neg = !do_neg;
}
}
void clr_dfs(int v, int c, int bnd) {
clr[v] = c;
for (auto to : g[v]) {
if (to == bnd) {
continue;
}
clr_dfs(to, c, bnd);
}
}
vector<mat<1, 3>> hld_dfs(int v, const vector<query>& a) {
int m = (int)a.size();
int u = v;
vector<int> way;
while ((int)g[u].size() != 0) {
way.push_back(u);
u = g[u][0];
}
way.push_back(u);
int k = (int)way.size();
for (int i = 0; i < k - 1; i += 1) {
clr_dfs(way[i], i, way[i + 1]);
}
clr[u] = k - 1;
vector<vector<query>> qrs(k);
for (auto& f : a) {
int i = clr[f.v];
qrs[i].push_back(f);
}
vector<vector<mat<1, 3>>> vals(k);
for (int i = 0; i < k; i += 1) {
if (i < k - 1) {
vals[i] = hld_dfs(g[way[i]][1], qrs[i]);
} else {
vals[i].resize((int)qrs[i].size() + 1);
vals[i][0] = val[way[i]];
for (int j = 0; j < (int)qrs[i].size(); j += 1) {
vals[i][j + 1] = { array<int, 3>{qrs[i][j].x, qrs[i][j].y, qrs[i][j].z} };
}
}
}
vector<mat<1, 3>> sgt_init(k - 1);
vector<int> p(k);
SGT sgt;
for (int i = 0; i < k - 1; i += 1) {
sgt_init[i] = vals[i][0];
p[i] = 1 + sz[g[way[i]][1]];
}
sgt.build(sgt_init, p);
p[k - 1] = 1;
for (int i = 0; i < k - 1; i += 1) {
clr_dfs(way[i], i, way[i + 1]);
}
clr[u] = k - 1;
vector<int> pntr(k);
vector<mat<1, 3>> rs(m + 1);
for (int i = 0; i <= m; i += 1) {
rs[i] = mul<1, 3, 3>(vals[k - 1][pntr[k - 1]], sgt.get());
/*
auto v = vals[k - 1][pntr[k - 1]];
for (int j = k - 2; j >= 0; j -= 1) {
v = mul<1, 3, 3>(v, get_matrix(vals[j][pntr[j]]));
}
rs[i] = v;
*/
if (i < m) {
int v = a[i].v;
int pos = clr[v];
pntr[pos] += 1;
if (pos < k - 1) {
sgt.chng(pos, vals[pos][pntr[pos]]);
}
}
}
return rs;
}
int32_t main() {
if (1) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
cin >> n >> q;
g.assign(n, vector<int>());
val.resize(n);
for (int i = 0; i < n; i += 1) {
char c;
cin >> c;
if (c == 'x') {
int l, r;
cin >> l >> r;
--l;
--r;
g[i] = { l, r };
} else {
int x, y, z;
cin >> x >> y >> z;
val[i] = { array<int, 3>{x, y, z} };
}
}
c = 0;
biba.resize(q);
for (auto& [v, x, y, z] : biba) {
cin >> v >> x >> y >> z;
--v;
}
do_neg = false;
sz.resize(n);
build_dfs(0);
clr.resize(n);
auto rs = hld_dfs(0, biba);
assert((int)rs.size() == q + 1);
for (int i = 1; i <= q; i += 1) {
int x = rs[i][0][0], y = rs[i][0][1], z = rs[i][0][2];
if (do_neg) {
x = neg(x);
y = neg(y);
z = neg(z);
}
cout << x << " " << y << " " << z << "\n";
}
return 0;
}
/*
5 3
x 2 3
v 1 0 1
x 4 5
v 0 2 1
v 1 1 1
4 1 2 3
5 0 1 1
4 0 2 2
*/