Given two three-dimensional vectors $$$v = (v_x, v_y, v_z)$$$ and $$$w = (w_x, w_y, w_z)$$$, recall that their cross product is another three-dimensional vector defined as $$$$$$ 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). $$$$$$ The cross product has length $$$\left| v \right| \left| w \right| \left| \sin \alpha \right|$$$, where $$$\alpha$$$ is the angle between $$$v$$$ and $$$w$$$ and its direction is such that $$$v \times w$$$ is at a right angle with both $$$v$$$ and $$$w$$$. Notice that if $$$v$$$ and $$$w$$$ have integer coordinates, then so does $$$v \times w$$$.
Recall that the cross product is not associative: that is, $$$(u \times v) \times w$$$ is not necessarily the same as $$$u \times (v \times w)$$$. Therefore, to reformulate classical data structure problems such as "update some values, calculate the maximum/sum/gcd of the array" with cross products, we need to specify which way the brackets are positioned. You're about to solve one such problem. To avoid expression parsing, we reformulate the problem in terms of trees (see how considerate we are!).
You are given a tree with $$$n$$$ vertices. The vertices are indexed $$$1 \ldots n$$$. Vertex 1 is the root. Each vertex is one of the following two types:
- Internal vertex. The vertex has exactly two children: a left child $$$l$$$ and a right child $$$r$$$.
- Leaf. The vertex has no children. A vector $$$(x, y, z)$$$ is written in the vertex.
- The value of an internal vertex $$$v$$$ is defined as $$$\mathrm{val}(l) \times \mathrm{val}(r)$$$, where $$$l$$$ and $$$r$$$ are the left and right child of $$$v$$$, respectively.
- The value of a leaf $$$v$$$ is defined as $$$(x, y, z)$$$, where $$$(x, y, z)$$$ is the vector written in the vertex $$$v$$$.
You are given $$$q$$$ queries of the following form:
- Given a leaf $$$v$$$ and a vector $$$(x, y, z)$$$. Replace the vector written in the vertex $$$v$$$ with $$$(x, y, z)$$$. Then print the value of the root vertex, i.e. $$$\mathrm{val}(1)$$$.
For each query, output the coordinates of the result modulo $$$P = 998\,244\,353$$$. That is, if the answer to a query is $$$(w_x, w_y, w_z)$$$, you may output any triple $$$(u_x, u_y, u_z)$$$ such that $$$w_x \equiv u_x \pmod{P}$$$, $$$w_y \equiv u_y \pmod{P}$$$ and $$$w_z \equiv u_z \pmod{P}$$$.
The first line of the input consists of two integers $$$n$$$ and $$$q$$$ ($$$3 \le n \le 2 \cdot 10^5$$$, $$$1 \le q \le 10^5$$$).
The following $$$n$$$ lines describe the vertices; the $$$i$$$-th of them describes the vertex $$$i$$$.
- If the $$$i$$$-th vertex is an internal vertex, then the line is of the form x $$$l$$$ $$$r$$$ ($$$2 \le l, r \le n$$$), where $$$l$$$ and $$$r$$$ are the indices of the left and right child, respectively.
- If the $$$i$$$-th vertex is a leaf, then the line is of the form v $$$x$$$ $$$y$$$ $$$z$$$ ($$$0 \le x, y, z \lt 998\,244\,353$$$), where $$$(x, y, z)$$$ is the vector written in the vertex $$$i$$$.
The following $$$q$$$ lines describe the queries. Each of them consists of four integers $$$v$$$, $$$x$$$, $$$y$$$, and $$$z$$$ ($$$1 \le v \le n$$$, $$$0 \le x, y, z \lt 998\,244\,353$$$). It is guaranteed that $$$v$$$ is a leaf.
For each query, print the answer on a separate line — three integers $$$x, y$$$ and $$$z$$$ ($$$-2^{31} \le x, y, z \lt 2^{31}$$$), the coordinates of the answer to the query, modulo $$$998\,244\,353$$$.
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
The following figures illustrate the state of the tree initially and after each query.
| Initial | Query 1 |
 |  |
| Query 2 | Query 3 |
 |  |
After the first query, the value of the root node is $$$ (1, 0, 1) \times ((1, 2, 3) \times (1, 1, 1)) = (-2, 0, 2) $$$. After the second query, the value of the root node is $$$ (1, 0, 1) \times ((1, 2, 3) \times (0, 1, 1)) = (1, -2, -1) $$$.
Notice that, as per the problem statement, both -2 and 998244351 are valid ways of outputting $$$-2$$$.
