NumberFactory 2.0

# H. NumberFactory 2.0

#### Problem Statement

You are again invited to LHS's top-secret facility, the number factory, as an inspector. However, different from last year, the number factory has received a massive upgrade by Egor :O! Instead of a monotonous line, the factory is now in the shape of a tree with $$N$$ nodes rooted at node $$1$$. Furthermore, instead of the boring $$+$$, $$-$$, and $$\times$$ operations, we now have the much more interesting bitwise operations: XOR, AND, OR. More specifically, each leaf node is assigned a number $$a_i$$, and each non-leaf node is assigned one of [XOR, AND, OR] as its operator $$b_i$$. The value of leaf node $$i$$ is just its assigned number $$a_i$$, whereas the value of a non-leaf node is the "sum" of all its children's values under the operator $$b_i$$. For example if $$c_1$$, $$c_2$$, $$c_3$$ are $$v$$'s children, and $$v$$'s operator is XOR, then its value is $$c_1$$ XOR $$c_2$$ XOR $$c_3$$.

Of course, as an inspector, you want to make sure all components of the factory are working properly, so you have $$M$$ queries of three types to perform. The first type asks what the value of node $$q_i$$ is. The second type changes the operator of non-leaf node $$q_i$$'s operator to $$o_i$$. The third type changes the assigned number of node $$q_i$$ to $$x_i$$. Note that any modification to node $$i$$ might cause other nodes to recalculate their values as well, such as its parent, and its parent's parent.

Time Limit:
C++: 2.5 seconds
Java, Python: 5 seconds
Memory Limit: 128mb

#### Constraints

$$2 \leq \sum M, N \leq 2 \cdot 10^5$$ and $$0 \leq a_i \leq 10^9$$

#### Input format

The first line contains integer $$T$$, the number of testcases. For each testcase, the first line contains $$2$$ numbers $$N$$, $$M$$.
The following $$N$$ lines describe the nodes, where line $$i$$ describes node $$i$$, containing 3 strings $$x$$, $$y$$, $$z$$:
- if $$x = 0$$, it is not a leaf node. $$y$$ is its parent node(with the exception for the first node, which in that case $$y$$ is always 0), and $$z$$ is one of [XOR, AND, OR]
- if $$x = 1$$, it is a leaf node. $$y$$ is its parent node, and $$z$$ is its assigned number $$a_i$$.
The next $$M$$ lines each describe a query. Let $$c$$ be the first character:
- if $$c = Q$$, it is the first type of query. The following number is $$q_i$$ and you have to output the corresponding node's current value.
- if $$c = R$$, it is the second type of query. The following two variables are $$x$$ and $$y$$, where you change non-leaf node $$x$$'s operator to $$y$$.
- if $$c = M$$, it is the third type of query. The following two numbers are $$x$$ and $$y$$, where you change leaf node $$x$$'s assigned number $$a_x$$ to $$y$$.

#### Output format

For each query of the first type, output node $$q_i$$'s current value after all the prior modifications.

1
6 5
0 0 XOR
1 1 3
0 1 OR
1 1 1
1 3 0
1 3 5
Q 3
M 2 3
M 6 6
R 3 XOR
Q 1

5
4

#### Sample Explanation

For the first query of the first type, node $$3$$'s value is the OR of nodes $$5$$ and $$6$$'s values, $$5$$ OR $$0 = 5$$.
For the second query, node $$3$$'s value is the XOR of node $$5$$ and node $$6$$'s values, $$6$$ XOR $$0 = 6$$. Subsequently, node $$1$$'s value is the XOR of nodes $$2$$, $$3$$, and $$4$$'s values, $$3$$ XOR $$6$$ XOR $$1 = 4$$. lexmathcsclub@gmail.com LIT Discord Server