给定两个三维向量 $v = (v_x, v_y, v_z)$ 和 $w = (w_x, w_y, w_z)$，回想它们的叉积是另一个定义为如下的三维向量： $$v \times w = (v_y w_z - v_z w_y, v_z w_x - v_x w_z, v_x w_y - v_y w_x)$$

叉积的长度为 $|v||w||\sin \alpha|$，其中 $\alpha$ 是 $v$ 和 $w$ 之间的夹角，其方向使得 $v \times w$ 与 $v$ 和 $w$ 都垂直。注意，如果 $v$ 和 $w$ 的坐标均为整数，则它们的叉积坐标也为整数。

回想叉积不满足结合律：即 $(u \times v) \times w$ 不一定等于 $u \times (v \times w)$。因此，为了用叉积重新表述诸如“更新某些值，计算数组的最大值/和/最大公约数”之类的经典数据结构问题，我们需要明确括号的位置。你即将解决这样一个问题。为了避免表达式解析，我们用树的形式重新表述了该问题。

给定一棵有 $n$ 个顶点的树。顶点编号为 $1 \dots n$。顶点 $1$ 是根。每个顶点属于以下两种类型之一： 内部节点：该顶点恰好有两个子节点：左子节点 $l$ 和右子节点 $r$。 叶子节点：该顶点没有子节点。顶点中写有一个向量 $(x, y, z)$。

顶点 $v$ 的值 $\text{val}(v)$ 是一个定义如下的三维向量： 内部节点 $v$ 的值定义为 $\text{val}(l) \times \text{val}(r)$，其中 $l$ 和 $r$ 分别是 $v$ 的左子节点和右子节点。 叶子节点 $v$ 的值定义为 $(x, y, z)$，其中 $(x, y, z)$ 是写在顶点 $v$ 中的向量。

给定 $q$ 个如下形式的查询： * 给定一个叶子节点 $v$ 和一个向量 $(x, y, z)$。将写在顶点 $v$ 中的向量替换为 $(x, y, z)$。然后输出根节点的值，即 $\text{val}(1)$。

对于每个查询，输出结果坐标对 $P = 998\,244\,353$ 取模后的值。也就是说，如果查询的答案是 $(w_x, w_y, w_z)$，你可以输出任何满足 $w_x \equiv u_x \pmod P$，$w_y \equiv u_y \pmod P$ 且 $w_z \equiv u_z \pmod P$ 的三元组 $(u_x, u_y, u_z)$。

输入格式

第一行包含两个整数 $n$ 和 $q$ ($3 \le n \le 2 \cdot 10^5, 1 \le q \le 10^5$)。 接下来的 $n$ 行描述顶点；第 $i$ 行描述顶点 $i$。 如果第 $i$ 个顶点是内部节点，则该行格式为 x l r ($2 \le l, r \le n$)，其中 $l$ 和 $r$ 分别是左子节点和右子节点的索引。 如果第 $i$ 个顶点是叶子节点，则该行格式为 v x y z ($0 \le x, y, z < 998\,244\,353$)，其中 $(x, y, z)$ 是写在顶点 $i$ 中的向量。

保证这些行描述了一棵以顶点 $1$ 为根的树。 接下来的 $q$ 行描述查询。每行包含四个整数 $v, x, y, z$ ($1 \le v \le n, 0 \le x, y, z < 998\,244\,353$)。保证 $v$ 是一个叶子节点。

输出格式

对于每个查询，在单独的一行中输出答案——三个整数 $x, y$ 和 $z$ ($-2^{31} \le x, y, z < 2^{31}$)，即查询结果的坐标，对 $998\,244\,353$ 取模。

样例

输入 1

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

输出 1

998244351 0 2
1 -2 998244352
0 0 0

说明

下图展示了树在初始状态以及每次查询后的状态。

第一次查询后，根节点的值为 $(1, 0, 1) \times ((1, 2, 3) \times (1, 1, 1)) = (-2, 0, 2)$。 第二次查询后，根节点的值为 $(1, 0, 1) \times ((1, 2, 3) \times (0, 1, 1)) = (1, -2, -1)$。 注意，根据题目描述，$-2$ 和 $998\,244\,351$ 都是表示 $-2$ 的有效方式。