#P18485. When Anton Saw This Task He Reacted With 😩

When Anton Saw This Task He Reacted With 😩

When Anton Saw This Task He Reacted With 😩

给定两个三维向量 v=(vx,vy,vz)v=(v_x,v_y,v_z) 和 w=(wx,wy,wz)w=(w_x,w_y,w_z),它们的叉积定义为

$$v\times w=(v_yw_z-v_zw_y,\ v_zw_x-v_xw_z,\ v_xw_y-v_yw_x).$$

叉积长度为 ∣v∣∣w∣∣sin⁡α∣|v||w||\sin\alpha|,其中 α\alpha 是两个向量的夹角;叉积方向同时垂直于 vv 和 ww。整数坐标向量的叉积仍有整数坐标。

叉积不满足结合律,也就是说 (u×v)×w(u\times v)\times w 不一定等于 u×(v×w)u\times(v\times w)。因此,若要支持修改一些向量并计算整个表达式的叉积,必须指定括号的位置。本题通过一棵树指定括号,无需解析表达式。

给定一棵 nn 个点的有根树,点编号为 1,2,…,n1,2,\ldots,n,根是点 11。每个点属于以下两类之一:

  • 内部点:恰好有两个孩子,分别为左孩子 ll、右孩子 rr。
  • 叶子:没有孩子,并写有一个向量 (x,y,z)(x,y,z)。

定义点 vv 的值 val⁡(v)\operatorname{val}(v):若为叶子,就是其写有的向量;若为内部点,则

$$\operatorname{val}(v)=\operatorname{val}(l)\times\operatorname{val}(r).$$

有 qq 次操作。每次给定一个叶子 vv 和一个向量 (x,y,z)(x,y,z),将该叶子写有的向量替换为 (x,y,z)(x,y,z),然后输出根的值 val⁡(1)\operatorname{val}(1)。

所有答案坐标均对 P=998 244 353P=998\,244\,353 取模。若某次操作后真实根向量为 (wx,wy,wz)(w_x,w_y,w_z),可以输出任何分别与这三个数模 PP 同余、且各自处于 signed32 范围的整数。

输入格式

第一行两个整数 n,qn,q(3≤n≤2⋅1053\le n\le2\cdot10^5,1≤q≤1051\le q\le10^5)。

随后 nn 行,第 ii 行描述点 ii:

  • 若为内部点,该行形式为 x l r,其中 2≤l,r≤n2\le l,r\le n。首个字符是小写字母 x,后面两个数依次为左、右孩子编号。
  • 若为叶子,该行形式为 v x y z,其中 0≤x,y,z<P0\le x,y,z<P。首个字符是小写字母 v,随后是该叶子上的向量。

保证这些行构成一棵以 11 为根的树。没有父节点编号小于孩子编号的额外保证。

随后 qq 行,每行四个整数 v x y z,表示一次替换操作。其中 1≤v≤n1\le v\le n,0≤x,y,z<P0\le x,y,z<P;保证 vv 是叶子。

输出格式

每次操作后输出一行三个整数 x,y,zx,y,z,分别与真实根向量的三个坐标模 PP 同余,并且都满足

−231≤x,y,z<231.-2^{31}\le x,y,z<2^{31}.

负数同余表示也合法。应当恰好输出 qq 个三元组。

原样例

输入:

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

输出:

998244351 0 2
1 -2 998244352
0 0 0

样例说明

以下四张原图依次表示初始状态、第一次操作后、第二次操作后和第三次操作后:

初始状态

第一次操作后

第二次操作后

第三次操作后

第一次操作后,根的值为 (1,0,1)×((1,2,3)×(1,1,1))=(−2,0,2)(1,0,1)\times((1,2,3)\times(1,1,1))=(-2,0,2)。

第二次操作后,根的值为 (1,0,1)×((1,2,3)×(0,1,1))=(1,−2,−1)(1,0,1)\times((1,2,3)\times(0,1,1))=(1,-2,-1)。

依照题意,输出 -2 和 998244351 都可以表示 −2-2。